TreeMap sort by value

Question

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 lt String  Integer gt  map   new TreeMap lt String  Integer gt  cmp           map put  de  10           map put  ab   20           map put  a  5            for  Map Entry lt String Integer gt  pair  map entrySet                  System out println pair getKey       pair getValue                        class byValue implements Comparator lt Map Entry lt String Integer gt  gt        public int compare Map Entry lt String Integer gt  e1  Map Entry lt String Integer gt  e2            if  e1 getValue    lt  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

User · Answer

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

User · Answer

import java util     public class Main    public static void main String   args        TreeMap lt String  Integer gt  initTree   new TreeMap        initTree put  quot D quot   0       initTree put  quot C quot   -3       initTree put  quot A quot   43       initTree put  quot B quot   32       System out println  quot Sorted by keys  quot        System out println initTree       List list   new ArrayList initTree entrySet         Collections sort list  new Comparator lt Map Entry lt String  Integer gt  gt               Override         public int compare Map Entry lt String  Integer gt  e1  Map Entry lt String  Integer gt  e2                return e1 getValue   compareTo e2 getValue                           System out println  quot Sorted by values  quot        System out println list

User · Answer

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

User · Answer

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  lt K V extends Comparable lt   super V gt  gt  SortedSet lt Map Entry lt K V gt  gt  entriesSortedByValues Map lt K V gt  map        SortedSet lt Map Entry lt K V gt  gt  sortedEntries   new TreeSet lt Map Entry lt K V gt  gt           new Comparator lt Map Entry lt K V gt  gt                   Override public int compare Map Entry lt K V gt  e1  Map Entry lt K V gt  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 lt String Integer gt  map   new TreeMap lt String Integer gt         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       Related questions   When comparing two Integers in Java does auto-unboxing occur   NO     Is it guaranteed that new Integer i     i in Java   YES

User · Answer

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  lt K V extends Comparable lt   super V gt  gt  SortedSet lt Map Entry lt K V gt  gt  entriesSortedByValues Map lt K V gt  map        SortedSet lt Map Entry lt K V gt  gt  sortedEntries   new TreeSet lt Map Entry lt K V gt  gt           new Comparator lt Map Entry lt K V gt  gt                   Override public int compare Map Entry lt K V gt  e1  Map Entry lt K V gt  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

User · Answer

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 lt Map Entry lt Integer  Double gt  gt  set   new TreeSet lt  gt  new Comparator lt Map Entry lt Integer  Double gt  gt             Override     public int compare Map Entry lt Integer  Double gt  o1  Map Entry lt Integer  Double gt  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 lt  gt  key  value

User · Answer

In Java 8   LinkedHashMap lt Integer  String gt  sortedMap        map entrySet   stream        sorted Entry comparingByValue         collect Collectors toMap Entry  getKey  Entry  getValue                                e1  e2  - gt  e1  LinkedHashMap  new

User · Answer

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 lt String  Integer gt  nonSortedMap   new HashMap lt String  Integer gt     nonSortedMap put  ape   1   nonSortedMap put  pig   3   nonSortedMap put  cow   1   nonSortedMap put  frog   2    for  Entry lt String  Integer gt  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  lt K V extends Comparable lt   super V gt  gt  SortedSet lt Map Entry lt K V gt  gt  entriesSortedByValues Map lt K V gt  map            SortedSet lt Map Entry lt K V gt  gt  sortedEntries   new TreeSet lt Map Entry lt K V gt  gt               new Comparator lt Map Entry lt K V gt  gt                       Override public int compare Map Entry lt K V gt  e1  Map Entry lt K V gt  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

User · Answer

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 lt Entry lt    Double gt  gt  DOUBLE VALUE COMPARATOR            new Comparator lt Entry lt    Double gt  gt                   Override             public int compare Entry lt    Double gt  o1  Entry lt    Double gt  o2                    return o1 getValue   compareTo o2 getValue                                       static final List lt Entry lt    Double gt  gt  sortHashMapByDoubleValue HashMap temp                        Set lt Entry lt    Double gt  gt  entryOfMap   temp entrySet                 List lt Entry lt    Double gt  gt  entries   new ArrayList lt Entry lt    Double gt  gt  entryOfMap               Collections sort entries  DOUBLE VALUE COMPARATOR               return entries

[java] TreeMap sort by value

Examples related to java