TreeMap sort by value

Java

Java Problem Overview

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?

Java Solutions

Solution 1 - Java

You can't have the TreeMap itself sort on the values, since that defies the SortedMap specification:

> A Map that further provides a total ordering on its keys.

However, using an external collection, you can always sort Map.entrySet() however you wish, either by keys, values, or even a combination(!!) of the two.

Here's a generic method that returns a SortedSet of Map.Entry, given a Map whose values are Comparable:

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;
			}
		}
	);
	sortedEntries.addAll(map.entrySet());
	return sortedEntries;
}

Now you can do the following:

    Map<String,Integer> map = new TreeMap<String,Integer>();
    map.put("A", 3);
    map.put("B", 2);
    map.put("C", 1);   

    System.out.println(map);
    // prints "{A=3, B=2, C=1}"
    System.out.println(entriesSortedByValues(map));
    // prints "[C=1, B=2, A=3]"

Note that funky stuff will happen if you try to modify either the SortedSet itself, or the Map.Entry within, because this is no longer a "view" of the original map like entrySet() is.

Generally speaking, the need to sort a map's entries by its values is atypical.

Note on == for Integer

Your original comparator compares Integer using ==. This is almost always wrong, since == with Integer operands is a reference equality, not value equality.

    System.out.println(new Integer(0) == new Integer(0)); // prints "false"!!!

Solution 2 - Java

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

Solution 3 - Java

In Java 8:

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

Solution 4 - Java

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.

Solution 5 - Java

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.

Solution 6 - Java

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.

Solution 7 - Java

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

Solution 8 - Java

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

Solution 9 - Java

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

Solution 10 - Java

//convert HashMap into List   
List<Entry<String, Integer>> list = new LinkedList<Entry<String, Integer>>(map.entrySet()); 

Collections.sort(list, (o1, o2) -> o1.getValue().compareTo(o2.getValue()));

Solution 11 - Java

If you want to use a Hash map you can add a condition in Comparator to check by values first & if values are equal perform a sort on keys

HashMap<String , Integer> polpularity = new HashMap<>();       
       List<String> collect = popularity.entrySet().stream().sorted((t2, t1) -> {
            if (t2.getValue() > t1.getValue()) {
                return -1;

            } else if (t2.getValue() < t1.getValue()) {
                return +1;

            } else {
                return t2.getKey().compareTo(t1.getKey());
            }
        }).map(entry -> entry.getKey()).collect(Collectors.toList());

If you don't want to take care of the latter condition then use a Treemap which will offer you sorting by itself, this can be done in an elegant single line of code:

 TreeMap<String, Integer> popularity = new TreeMap<>();

 List<String> collect = popularity.entrySet().stream().sorted(Collections.reverseOrder(Map.Entry.comparingByValue())).map(entry -> entry.getKey()).collect(Collectors.toList());

Categories
Recommended Java Solutions

Previous Solution:

Allowed characters in Linux environment variable names

LinuxSyntaxEnvironment Variables

Next Solution:

Where can I find the Java JDK source code?

Java

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
Questionvito huangView Question on Stackoverflow
Solution 1 - JavapolygenelubricantsView Answer on Stackoverflow
Solution 2 - JavaOlof LarssonView Answer on Stackoverflow
Solution 3 - JavaVitalii FedorenkoView Answer on Stackoverflow
Solution 4 - JavaMichael BorgwardtView Answer on Stackoverflow
Solution 5 - JavaJoachim SauerView Answer on Stackoverflow
Solution 6 - JavaHalogenView Answer on Stackoverflow
Solution 7 - JavaPaul JacksonView Answer on Stackoverflow
Solution 8 - JavazinaView Answer on Stackoverflow
Solution 9 - JavaDmitry IvanovView Answer on Stackoverflow
Solution 10 - JavaKanagavelu SugumarView Answer on Stackoverflow
Solution 11 - JavaGruView Answer on Stackoverflow