Sort a Map<Key, Value> by values

Question

Here's a generic-friendly version:

public class MapUtil {
    public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) {
        List<Entry<K, V>> list = new ArrayList<>(map.entrySet());
        list.sort(Entry.comparingByValue());

        Map<K, V> result = new LinkedHashMap<>();
        for (Entry<K, V> entry : list) {
            result.put(entry.getKey(), entry.getValue());
        }

        return result;
    }
}

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}

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));

Or print to System.out:

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

Three 1-line answers...

I would use Google Collections Guava to do this - if your values are Comparable then you can use

valueComparator = Ordering.natural().onResultOf(Functions.forMap(map))

Which will create a function (object) for the map [that takes any of the keys as input, returning the respective value], and then apply natural (comparable) ordering to them [the values].

If they're not comparable, then you'll need to do something along the lines of

valueComparator = Ordering.from(comparator).onResultOf(Functions.forMap(map)) 

These may be applied to a TreeMap (as Ordering extends Comparator), or a LinkedHashMap after some sorting

NB: If you are going to use a TreeMap, remember that if a comparison == 0, then the item is already in the list (which will happen if you have multiple values that compare the same). To alleviate this, you could add your key to the comparator like so (presuming that your keys and values are Comparable):

valueComparator = Ordering.natural().onResultOf(Functions.forMap(map)).compound(Ordering.natural())

= Apply natural ordering to the value mapped by the key, and compound that with the natural ordering of the key

Note that this will still not work if your keys compare to 0, but this should be sufficient for most comparable items (as hashCode, equals and compareTo are often in sync...)

See Ordering.onResultOf() and Functions.forMap().

Implementation

So now that we've got a comparator that does what we want, we need to get a result from it.

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

Now this will most likely work work, but:

1. needs to be done given a complete finished map
2. Don't try the comparators above on a TreeMap; there's no point trying to compare an inserted key when it doesn't have a value until after the put, i.e., it will break really fast

Point 1 is a bit of a deal-breaker for me; google collections is incredibly lazy (which is good: you can do pretty much every operation in an instant; the real work is done when you start using the result), and this requires copying a whole map!

"Full" answer/Live sorted map by values

Don't worry though; if you were obsessed enough with having a "live" map sorted in this manner, you could solve not one but both(!) of the above issues with something crazy like the following:

Note: This has changed significantly in June 2012 - the previous code could never work: an internal HashMap is required to lookup the values without creating an infinite loop between the TreeMap.get() -> compare() and compare() -> get()

import static org.junit.Assert.assertEquals;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

import com.google.common.base.Functions;
import com.google.common.collect.Ordering;

class ValueComparableMap<K extends Comparable<K>,V> extends TreeMap<K,V> {
    //A map for doing lookups on the keys for comparison so we don't get infinite loops
    private final Map<K, V> valueMap;

    ValueComparableMap(final Ordering<? super V> partialValueOrdering) {
        this(partialValueOrdering, new HashMap<K,V>());
    }

    private ValueComparableMap(Ordering<? super V> partialValueOrdering,
            HashMap<K, V> valueMap) {
        super(partialValueOrdering //Apply the value ordering
                .onResultOf(Functions.forMap(valueMap)) //On the result of getting the value for the key from the map
                .compound(Ordering.natural())); //as well as ensuring that the keys don't get clobbered
        this.valueMap = valueMap;
    }

    public V put(K k, V v) {
        if (valueMap.containsKey(k)){
            //remove the key in the sorted set before adding the key again
            remove(k);
        }
        valueMap.put(k,v); //To get "real" unsorted values for the comparator
        return super.put(k, v); //Put it in value order
    }

    public static void main(String[] args){
        TreeMap<String, Integer> map = new ValueComparableMap<String, Integer>(Ordering.natural());
        map.put("a", 5);
        map.put("b", 1);
        map.put("c", 3);
        assertEquals("b",map.firstKey());
        assertEquals("a",map.lastKey());
        map.put("d",0);
        assertEquals("d",map.firstKey());
        //ensure it's still a map (by overwriting a key, but with a new value) 
        map.put("d", 2);
        assertEquals("b", map.firstKey());
        //Ensure multiple values do not clobber keys
        map.put("e", 2);
        assertEquals(5, map.size());
        assertEquals(2, (int) map.get("e"));
        assertEquals(2, (int) map.get("d"));
    }
 }

When we put, we ensure that the hash map has the value for the comparator, and then put to the TreeSet for sorting. But before that we check the hash map to see that the key is not actually a duplicate. Also, the comparator that we create will also include the key so that duplicate values don't delete the non-duplicate keys (due to == comparison). These 2 items are vital for ensuring the map contract is kept; if you think you don't want that, then you're almost at the point of reversing the map entirely (to Map<V,K>).

The constructor would need to be called as

 new ValueComparableMap(Ordering.natural());
 //or
 new ValueComparableMap(Ordering.from(comparator));

From http://www.programmersheaven.com/download/49349/download.aspx

private static <K, V> Map<K, V> sortByValue(Map<K, V> map) {
    List<Entry<K, V>> list = new LinkedList<>(map.entrySet());
    Collections.sort(list, new Comparator<Object>() {
        @SuppressWarnings("unchecked")
        public int compare(Object o1, Object o2) {
            return ((Comparable<V>) ((Map.Entry<K, V>) (o1)).getValue()).compareTo(((Map.Entry<K, V>) (o2)).getValue());
        }
    });

    Map<K, V> result = new LinkedHashMap<>();
    for (Iterator<Entry<K, V>> it = list.iterator(); it.hasNext();) {
        Map.Entry<K, V> entry = (Map.Entry<K, V>) it.next();
        result.put(entry.getKey(), entry.getValue());
    }

    return result;
}

With Java 8, you can use the streams api to do it in a significantly less verbose way:

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