How to improve sorting on values of a Map via Collections

Question

I often get into situation when I need to sort a Map on values. Maps are not meant for that in JDK and I decided not to use Guava (seems like this stuff is one liner but I didn't quite get it) nor Apache Commons, so I do it this way. Btw this is a very popular question, but most of the answers are wrong in one way or another.

    Map<String, Long> map = new HashMap<String, Long>();
    // populate
    List<Map.Entry<String, Long>> list = new LinkedList<Map.Entry<String,Long>>();
    for (Map.Entry<String, Long> entry : map.entrySet()) {
        list.add(entry);
    }
    Collections.sort(list, new MapComparable());
    LinkedHashMap<String, Long> linkedMap = new LinkedHashMap<String, Long>();

    for (Map.Entry<String, Long> entry : list) {
        linkedMap.put(entry.getKey(), entry.getValue());
    }
}

    public static class MapComparable implements Comparator<Map.Entry<String, Long>>{

        public int compare(Entry<String, Long> e1, Entry<String, Long> e2) {
            return (e1.getValue()<e2.getValue() ? -1 : (e1.getValue()==e2.getValue() ? 0 : 1));
        }
    }

My question is, is there a better way of getting the EntrySet to / from Collection ? It doesn't look good.

And is this reliable ?

Why sort on value? I would say that what you have created is fragile. The map would no longer be sorted if you modify the `LinkedHashMap` — Kaj, Jun 03 '11 at 22:20
Why not. There are cases ... This is for one time thing, sort it and return ... — lisak, Jun 03 '11 at 22:22
@Kaj you would sort on values if you wanted keys that were similar. Think of a thesaurus which is a special type of dictionary. — Woot4Moo, Jun 03 '11 at 22:29
I need it for sorting n-gram files for language detection. A map with 'cop' : 4213, 'dec' : 9877, etc — lisak, Jun 03 '11 at 22:30
Yeah, I find myself in need of sorting map on values all the time. Usually at the end of some processing or persisting results... — lisak, Jun 03 '11 at 22:41

score 2 · Answer 1 · answered Jun 03 '11 at 22:19

2

You could maintain a dual data structure, one set as a Map that provides string -> long conversions, and the other as a List or similar structure that provides ordered conversions, with an overall structure to maintain both together.

answered Jun 03 '11 at 22:19

Guvante

18,775
1
33
64

Well, there are really tons of ways to do that.I like this one, it is straightforward and easily understandable for others ... The problem of it is moving EntrySet to/from the collection for sorting, cause it makes it look ugly. Which is what the question is about. – lisak Jun 03 '11 at 22:25
@lisak: There is no other way to do it to my knowledge, you can't take a random list of integers and sort it without parsing the entire list. You could use helper functions to make the main method cleaner, but that algorithm is probably the best you are going to get. – Guvante Jun 03 '11 at 22:34

trutheality · Accepted Answer · 2011-06-04T08:52:12.790

What I think is a very slight improvement to your method is:

Queue queue = new PriorityQueue( map.size(), new MapComparable() );

queue.addAll( map.entrySet() );

LinkedHashMap<String, Long> linkedMap = new LinkedHashMap<String, Long>();

for (Map.Entry<String, Long> entry; (entry = queue.poll())!=null;) {
    linkedMap.put(entry.getKey(), entry.getValue());
}

In other words, do the sorting with a datastructure designed for sorting.

As a general note, code like

for (Map.Entry<String, Long> entry : map.entrySet()) {
    list.add(entry);
}

Can be shortened to:

list.addAll( map.entrySet() );

whenever you're dealing with Collections.

Also I think this:

public int compare(Entry<String, Long> e1, Entry<String, Long> e2) {
    return e1.getValue().compareTo(e2.getValue());
}

is cleaner.

How to improve sorting on values of a Map via Collections

2 Answers2