Thursday, June 9, 2011

Generic method to sort a Map according to Values

We all have at least once used classes implementing java.util.Map. Some of the most prominent ones are
  • HashMap
  • TreeMap
  • LinkedHashMap
Of these, HashMap and LinkedHashMap do not sort the entries. TreeMap sorts the entries according to the natural order of the set of keys in the map. Hence it becomes very trivial to store key-value mappings ordered by the keys.

HashMaps and LinkedHashMaps on the other hand do not sort its entries. LinkedHashMap does however guarantee a insertion order [or in some cases fetching order] in its entries. HashMaps do not guarantee even that. There are times when we want the map entries to be ordered according to the values instead of keys.


So, following is a generic method  that will sort a given map. The method is generic and will work with any maps provided it has the following property:

The values of the map must have a natural order.

It basically means that the Values must implement the java.util.Comparable interface. The reason for this requirement is that, since this is a generic method, it will not know how to sort the values. It must rely on its natural ordering. Of course the method can be further overloaded to use a Comparator instance so that instead of natural ordering, it can sort the entries according to some other contextual order.

Enough theory, here it goes:
/**

 * Sort a map according to values.

 * @param  < K >  the key of the map.
 * @param  < V >  the value to sort according to.
 * @param mapToSort the map to sort.

 * @return a map sorted on the values.

 */  

public static  < K, V extends Comparable < ? super V >  >  Map < K, V > 
sortMapByValues(final Map  < K, V >  mapToSort)
{
    List < Map.Entry < K, V >  >  entries =
        new ArrayList < Map.Entry < K, V >  > (mapToSort.size());  

    entries.addAll(mapToSort.entrySet());

    Collections.sort(entries,
                     new Comparator < Map.Entry < K, V >  > ()
    {
        @Override
        public int compare(
               final Map.Entry < K, V >  entry1,
               final Map.Entry < K, V >  entry2)
        {
            return entry1.getValue().compareTo(entry2.getValue());
        }
    });      

    Map < K, V >  sortedMap = new LinkedHashMap < K, V > ();      

    for (Map.Entry < K, V >  entry : entries)
    {
        sortedMap.put(entry.getKey(), entry.getValue());
    }      

    return sortedMap;
}
Feel free to use it, twist it in whatever convoluted way you want.

Happy coding!

5 comments:

  1. Good article. just to add while using comparable interface in Java and overriding compareTo method its worth noting that compareTo must be compatible with s equals method in Java i.e. if two objects are equal via equals method compareTo method must return "0" for them, failing this may result in some subtle bug when you store those objects in collection class like Arraylist in Java.

    Source: How to use Comparator and Comparable in Java

    ReplyDelete
    Replies
    1. Good point! To make it more complete: there is a valid way to break the compatibility between compareTo() and equals(): don't make the class Comparable, instead, implement independent Comparators (these are valid if you want to compare this class by multiple, special means).

      Delete
  2. how to convert "return sortedMap;" to List mylist = null;

    ReplyDelete
  3. Hi Swaranga,
    I loved reading this piece! Well written! :)

    jason
    RMP Properties

    ReplyDelete
  4. Good article. I liked it.
    Thank you

    ReplyDelete