Sorting HashMaps by value

Question

When I need to sort a HashMap by value, the advice seems to be to create the HashMap and then put the data into a TreeMap which is sorted by value.

For example: Sort a Map<Key, Value> by values (Java)

My question: why is it necessary to do this? Why not create a TreeMap(which is sorted by keys) and then sort it in place by value?

score 2 · Answer 1 · edited May 23 '17 at 12:31

2

Because you can't reorder the entries of a TreeMap manually. TreeMap entries are always sorted on the keys.

I'm going to throw out Map that could be iterated in the order of values as another answer to "How to do it," though...specifically, a solution which doesn't return a map that chokes (by throwing exceptions) on queries to keys not in your original map.

edited May 23 '17 at 12:31

Community

1
1

answered Feb 06 '12 at 22:29

Louis Wasserman

191,574
25
345
413

Just a note, if you bothered to read the question referenced in the OP, you would notice that TreeMaps are ***not*** always sorted on the keys. Treemaps can accept a comparator which allows them to be sorted on pretty much anything (including values). – gnomed Feb 06 '12 at 22:39
1

I think it's probably easier for me to put the values in an array and then sort that. – Tom Kealy Feb 06 '12 at 23:05
1

@gnomed: The TreeMap is always sorting on the keys, though it might be sorting according to some wacky comparator (that could quite possibly be looking up the values from elsewhere). I did, in fact, read the question referenced in the OP, though it suggested a technique that's frankly quite prone to wacky bugs when you try `map.containsKey(keyNotInOriginalMap)` and suddenly you're getting very confusing exceptions and have no idea why you're getting them. – Louis Wasserman Feb 07 '12 at 00:03
@TomKealy: If you're going to do that approach, then there are convenient ways to do it -- don't use an array. For example, `List theValues = new ArrayList(map.values()); Collections.sort(theValues);` – Louis Wasserman Feb 07 '12 at 00:04
OK, that is what I wanted to do. However, my original question was why create a HashMap and then put things in a TreeMap but lookup by keys - is there a better way that avoids the use of two objects (in Java - for example a bash script will do this in one line). The way I'm doing it seemsa bit redundant. – Tom Kealy Feb 07 '12 at 11:04
There isn't a way that does it without an intermediate object, not without a massive amount of effort. – Louis Wasserman Feb 07 '12 at 19:31

Samir Talwar · Accepted Answer · 2012-02-07T00:31:31.617

If you know your values to be unique, you can use Guava's BiMap (bidirectional map) to store the data. Create a HashBiMap as you would your HashMap, then create a new TreeMap from its inverse:

new TreeMap<>(biMap.inverse());

That map will then be sorted by the values. Remember that what you're thinking of as "keys" and "values" will be swapped.

If your values are not unique, you can create a multimap of the inverse. A multimap is essentially a mapping from each key to one or more values. It's usually implemented by making a map from a key to a list. You don't have to do that though, because Google did it for you. Just create a multimap from your existing map, and ask Guava to invert it for you into a TreeMultimap, which, as you can guess, is a TreeMap that can hold multiple values per key.

Multimaps.invertFrom(Multimaps.forMap(myMap), new TreeMultimap<V, K>());

Multimap documentation is provided.

Alas, my values may not be unique but I'll keep that in mind for the future. — Tom Kealy, Feb 06 '12 at 23:00

score 1 · Answer 3 · edited May 10 '16 at 10:39

I have this very small code which is working fine:

public class SortMapByValues {
    public static void main(String[] args) {

        Map<Integer, String> myMap = new LinkedHashMap<Integer, String>();

        myMap.put(100, "hundread");
        myMap.put(500, "fivehundread");
        myMap.put(250, "twofifty");
        myMap.put(300, "threehundread");
        myMap.put(350, "threefifty");
        myMap.put(400, "fourhundread");

        myMap = sortMapByValues(myMap);

        for (Map.Entry<Integer, String> entry : myMap.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }

    }

    public static Map<Integer, String> sortMapByValues(
            Map<Integer, String> firstMap) {
        Map<String, Integer> SecondyMap = new TreeMap<String, Integer>();

        for (Map.Entry<Integer, String> entry : firstMap.entrySet()) {
            SecondyMap.put(entry.getValue(), entry.getKey());
        }
        firstMap.clear();
        for (Map.Entry<String, Integer> entry : SecondyMap.entrySet()) {
            firstMap.put(entry.getValue(), entry.getKey());
        }
        return firstMap;
    }

}

Output:

500 fivehundread  
400 fourhundread  
100 hundread  
350 threefifty  
300 threehundread  
250 twofifty

score 1 · Answer 4 · answered May 10 '16 at 10:46

I wrote the following one-liner using Java 8 Stream API to sort any given map by value:

List<Map.Entry<String, String>> sortedEntries = map.entrySet().stream()
  .sorted((o1, o2) -> o1.getValue().compareTo(o2.getValue())).collect(Collectors.toList());

Sorting HashMaps by value

4 Answers4