Categories
collections dictionary java sorting

Sort a Map by values

1823

I am relatively new to Java, and often find that I need to sort a Map<Key, Value> on the values.

Since the values are not unique, I find myself converting the keySet into an array, and sorting that array through array sort with a custom comparator that sorts on the value associated with the key.

Is there an easier way?

7

  • 31

    A map is not meant to be sorted, but accessed fast. Object equal values break the constraint of the map. Use the entry set, like List<Map.Entry<...>> list =new LinkedList(map.entrySet()) and Collections.sort .... it that way.

    – Hannes

    Feb 9, 2014 at 17:34


  • 2

    A case where this might arise when we try to make use of a Counter in Java (Map<Object, Integer>). Sorting by number of occurrences would then be a common operation. A language like Python has a built in Counter data structure. For an alternate way of implementation in Java, here is an example

    Dec 21, 2017 at 20:03

  • 13

    There are plenty of use cases for sorted maps, that’s why you have TreeMap and ConcurrentSkipListMap in jdk.

    – alobodzk

    Apr 22, 2018 at 19:10

  • 8

    TreeMap and ConcurrentSkipListMap sort by key. The question is about sorting by value.

    – Peter

    Apr 28, 2020 at 12:28

  • 3

    I’d like to add that depending on your use case, it may be reasonable to simply keep a duplicate TreeMap that maps your value to your keys. For example, your regular map may have “a” -> 5, “b” -> 7″. And your “sorted” map can have 5 -> “a”, 7 -> “b”. You would just use whichever map is appropriate in different places and make an effort to always modify the two maps together. It’s not pretty and there are many caveats and assumptions, but for some cases it can be a straightforward and efficient answer compared to all the top answers here which rely on actively sorting your values.

    – rococo

    Jul 12, 2021 at 6:45


432

Important note:

This code can break in multiple ways. If you intend to use the code provided, be sure to read the comments as well to be aware of the implications. For example, values can no longer be retrieved by their key. (get always returns null.)


It seems much easier than all of the foregoing. Use a TreeMap as follows:

public class Testing {
    public static void main(String[] args) {
        HashMap<String, Double> map = new HashMap<String, Double>();
        ValueComparator bvc = new ValueComparator(map);
        TreeMap<String, Double> sorted_map = new TreeMap<String, Double>(bvc);

        map.put("A", 99.5);
        map.put("B", 67.4);
        map.put("C", 67.4);
        map.put("D", 67.3);

        System.out.println("unsorted map: " + map);
        sorted_map.putAll(map);
        System.out.println("results: " + sorted_map);
    }
}

class ValueComparator implements Comparator<String> {
    Map<String, Double> base;

    public ValueComparator(Map<String, Double> base) {
        this.base = base;
    }

    // Note: this comparator imposes orderings that are inconsistent with
    // equals.
    public int compare(String a, String b) {
        if (base.get(a) >= base.get(b)) {
            return -1;
        } else {
            return 1;
        } // returning 0 would merge keys
    }
}

Output:

unsorted map: {D=67.3, A=99.5, B=67.4, C=67.4}
results: {D=67.3, B=67.4, C=67.4, A=99.5}

16

  • 18

    Not any more (stackoverflow.com/questions/109383/…). Also, why was there a cast to Double? Shouldn’t it just be return ((Comparable)base.get(a).compareTo(((Comparable)base.get(b)))?

    – Stephen

    Aug 11, 2010 at 21:50

  • 12

    @Stephen: No. In this case all keys equal by value are dropped (difference between equals and comparion by reference). Additionally: Even this code has problems with the following sequence map.put("A","1d");map.put("B","1d");map.put("C",67d);map.put("D",99.5d);

    – mlwida

    Aug 20, 2010 at 7:00

  • 43

    The comparator used for the treemap is inconsistent with equals (see the sortMap javadox). This means retireving items from the tree map will not work. sorted_map.get(“A”) will return null. That means this use of treemap is broken.

    – mR_fr0g

    Dec 1, 2010 at 14:36

  • 90

    Just in case it’s not clear to people: this solution will probably not do what you want if you have multiple keys mapping to the same value — only one of those keys will appear in the sorted result.

    – Maxy-B

    Nov 24, 2011 at 4:37

  • 63

    Louis Wasserman (yes, one of the Google Guava guys), actually dislikes this answer quite a bit: “It breaks in several really confusing ways if you even look at it funny. If the backing map changes, it will break. If multiple keys map to the same value, it will break. If you call get on a key that isn’t in the backing map, it will break. If you do anything whatsoever that would cause a lookup to happen on a key that isn’t in the map — a Map.equals call, containsKey, anything — it will break with really weird stack traces.” plus.google.com/102216152814616302326/posts/bEQLDK712MJ

    – haylem

    Jul 3, 2012 at 21:19

430

Java 8 offers a new answer: convert the entries into a stream, and use the comparator combinators from Map.Entry:

Stream<Map.Entry<K,V>> sorted =
    map.entrySet().stream()
       .sorted(Map.Entry.comparingByValue());

This will let you consume the entries sorted in ascending order of value. If you want descending value, simply reverse the comparator:

Stream<Map.Entry<K,V>> sorted =
    map.entrySet().stream()
       .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()));

If the values are not comparable, you can pass an explicit comparator:

Stream<Map.Entry<K,V>> sorted =
    map.entrySet().stream()
       .sorted(Map.Entry.comparingByValue(comparator));

You can then proceed to use other stream operations to consume the data. For example, if you want the top 10 in a new map:

Map<K,V> topTen =
    map.entrySet().stream()
       .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
       .limit(10)
       .collect(Collectors.toMap(
          Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));

The LinkedHashMap seen above iterates entries in the order in which they were inserted.

Or print to System.out:

map.entrySet().stream()
   .sorted(Map.Entry.comparingByValue())
   .forEach(System.out::println);

12

  • Nice, but what about the use of parallelStream() in this case ?

    – Benj

    Dec 9, 2014 at 18:21


  • 12

    It will work in parallel, however, you may find that the cost of merging maps to combine the partial results is too expensive and the parallel version may not perform as well as you’d hope. But it does work and produce the correct answer.

    Dec 9, 2014 at 18:37

  • 2

    don’ t you have to use compareByValue in the top10 example?

    – Leo

    Aug 19, 2016 at 23:34

  • 1

    The part for making up a top ten is incorrect, you need to add two more parameters as posted here: stackoverflow.com/a/19671853/5655767

    – Steven

    Aug 21, 2017 at 11:19

  • 1

    @Benj it will work in terms of extracting the top-10, but the resulting map will no longer be ordered.

    – OrangeDog

    Jun 18, 2019 at 14:30