[java] TreeMap sort by value

I want to write a comparator that will let me sort a TreeMap by value instead of the default natural ordering.

I tried something like this, but can't find out what went wrong:

import java.util.*;

class treeMap {
    public static void main(String[] args) {
        System.out.println("the main");
        byValue cmp = new byValue();
        Map<String, Integer> map = new TreeMap<String, Integer>(cmp);
        map.put("de",10);
        map.put("ab", 20);
        map.put("a",5);

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

class byValue implements Comparator<Map.Entry<String,Integer>> {
    public int compare(Map.Entry<String,Integer> e1, Map.Entry<String,Integer> e2) {
        if (e1.getValue() < e2.getValue()){
            return 1;
        } else if (e1.getValue() == e2.getValue()) {
            return 0;
        } else {
            return -1;
        }
    }
}

I guess what am I asking is: Can I get a Map.Entry passed to the comparator?

I know this post specifically asks for sorting a TreeMap by values, but for those of us that don't really care about implementation but do want a solution that keeps the collection sorted as elements are added, I would appreciate feedback on this TreeSet-based solution. For one, elements are not easily retrieved by key, but for the use case I had at hand (finding the n keys with the lowest values), this was not a requirement.

  TreeSet<Map.Entry<Integer, Double>> set = new TreeSet<>(new Comparator<Map.Entry<Integer, Double>>()
  {
    @Override
    public int compare(Map.Entry<Integer, Double> o1, Map.Entry<Integer, Double> o2)
    {
      int valueComparison = o1.getValue().compareTo(o2.getValue());
      return valueComparison == 0 ? o1.getKey().compareTo(o2.getKey()) : valueComparison;
    }
  });
  int key = 5;
  double value = 1.0;
  set.add(new AbstractMap.SimpleEntry<>(key, value));

This can't be done by using a Comparator, as it will always get the key of the map to compare. TreeMap can only sort by the key.

import java.util.*;

public class Main {

public static void main(String[] args) {
    TreeMap<String, Integer> initTree = new TreeMap();
    initTree.put("D", 0);
    initTree.put("C", -3);
    initTree.put("A", 43);
    initTree.put("B", 32);
    System.out.println("Sorted by keys:");
    System.out.println(initTree);
    List list = new ArrayList(initTree.entrySet());
    Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
        @Override
        public int compare(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) {
            return e1.getValue().compareTo(e2.getValue());
        }
    });
    System.out.println("Sorted by values:");
    System.out.println(list);
}
}

Olof's answer is good, but it needs one more thing before it's perfect. In the comments below his answer, dacwe (correctly) points out that his implementation violates the Compare/Equals contract for Sets. If you try to call contains or remove on an entry that's clearly in the set, the set won't recognize it because of the code that allows entries with equal values to be placed in the set. So, in order to fix this, we need to test for equality between the keys:

static <K,V extends Comparable<? super V>> SortedSet<Map.Entry<K,V>> entriesSortedByValues(Map<K,V> map) {
    SortedSet<Map.Entry<K,V>> sortedEntries = new TreeSet<Map.Entry<K,V>>(
        new Comparator<Map.Entry<K,V>>() {
            @Override public int compare(Map.Entry<K,V> e1, Map.Entry<K,V> e2) {
                int res = e1.getValue().compareTo(e2.getValue());
                if (e1.getKey().equals(e2.getKey())) {
                    return res; // Code will now handle equality properly
                } else {
                    return res != 0 ? res : 1; // While still adding all entries
                }
            }
        }
    );
    sortedEntries.addAll(map.entrySet());
    return sortedEntries;
}

"Note that the ordering maintained by a sorted set (whether or not an explicit comparator is provided) must be consistent with equals if the sorted set is to correctly implement the Set interface... the Set interface is defined in terms of the equals operation, but a sorted set performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal." (http://docs.oracle.com/javase/6/docs/api/java/util/SortedSet.html)

Since we originally overlooked equality in order to force the set to add equal valued entries, now we have to test for equality in the keys in order for the set to actually return the entry you're looking for. This is kinda messy and definitely not how sets were intended to be used - but it works.

A TreeMap is always sorted by the keys, anything else is impossible. A Comparator merely allows you to control how the keys are sorted.

If you want the sorted values, you have to extract them into a List and sort that.

polygenelubricants answer is almost perfect. It has one important bug though. It will not handle map entries where the values are the same.

This code:...

Map<String, Integer> nonSortedMap = new HashMap<String, Integer>();
nonSortedMap.put("ape", 1);
nonSortedMap.put("pig", 3);
nonSortedMap.put("cow", 1);
nonSortedMap.put("frog", 2);

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

Would output:

ape:1
frog:2
pig:3

Note how our cow dissapeared as it shared the value "1" with our ape :O!

This modification of the code solves that issue:

static <K,V extends Comparable<? super V>> SortedSet<Map.Entry<K,V>> entriesSortedByValues(Map<K,V> map) {
        SortedSet<Map.Entry<K,V>> sortedEntries = new TreeSet<Map.Entry<K,V>>(
            new Comparator<Map.Entry<K,V>>() {
                @Override public int compare(Map.Entry<K,V> e1, Map.Entry<K,V> e2) {
                    int res = e1.getValue().compareTo(e2.getValue());
                    return res != 0 ? res : 1; // Special fix to preserve items with equal values
                }
            }
        );
        sortedEntries.addAll(map.entrySet());
        return sortedEntries;
    }

A lot of people hear adviced to use List and i prefer to use it as well

here are two methods you need to sort the entries of the Map according to their values.

    static final Comparator<Entry<?, Double>> DOUBLE_VALUE_COMPARATOR = 
        new Comparator<Entry<?, Double>>() {
            @Override
            public int compare(Entry<?, Double> o1, Entry<?, Double> o2) {
                return o1.getValue().compareTo(o2.getValue());
            }
        };

        static final List<Entry<?, Double>> sortHashMapByDoubleValue(HashMap temp)
        {
            Set<Entry<?, Double>> entryOfMap = temp.entrySet();

            List<Entry<?, Double>> entries = new ArrayList<Entry<?, Double>>(entryOfMap);
            Collections.sort(entries, DOUBLE_VALUE_COMPARATOR);
            return entries;
        }

In Java 8:

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