Wednesday, December 19, 2012

How to sort HashMap by key and value in Java - Hashtable, Map Example Tutorial

Sorting HashMap in Java is not as easy as it sounds because unfortunately Java API doesn't provide any utility method to sort HashMap based on keys and values. Sorting HashMap is not like sorting ArrayList or sorting Arrays in Java. If you are wondering why we can not use Collections.sort() method than for your information it only accepts List<E>, which leaves us to write our own utility methods to sort Map in Java. This is true for all types of Map like Hashtable, HashMap and LinkedHashMap. TreeMap is an already a sorted Map so we don't need to sort it again. Why we need to sort HashMap in Java, Why can't we use TreeMap in place of HashMap is the question appears in most Java programmer's mind when they asked to sort HashMap in Java. Well TreeMap is way slower than HashMap because it runs sorting operation with each insertion, update and removal and some time you don't really need an all time sorted Map, What you need is an ability to sort any Map implementation based upon its key and value. In last couple of articles we have seen How to loop or traverse Map in Java and in this Java tutorial we will see couple of ways to sort HashMap in Java.


Sorting Map in Java - By Key

How to sort Map in Java based on keys and values with example
As I said Map or HashMap in Java can be sorted either on keys or values. Sorting Map on keys is rather easy than sorting on values because Map allows duplicate values but doesn't allow duplicates keys. You can sort Map, be it HashMap or Hashtable by copying keys into List than sorting List by using Collections.sort() method, here you can use either Comparator or Comparable based upon whether you want to sort on custom order or natural order. Once List of keys are sorted, we can create another Map, particularly LinkedHashMap to insert keys in sorted order. LinkedHashMap will maintain the order on which keys are inserted, result is a sorted Map based on keys. This is shown in following example by writing a generic parameterized method to sort Map based on keys. You can also sort Map in Java by using TreeMap and Google Collection API (Guava). Advantage of using Guava is that you get some flexibility on specifying ordering.


Sorting Map in Java - By Value

Sorting Map in Java e.g. HashMap or Hashtable based upon values is more difficult than sorting Map based on keys, because Map allows duplicate values and You also get challenge to handle null values.

package test;

import com.google.common.collect.Maps;
import com.google.common.collect.Ordering;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

/**
 *
 * Java program to demonstrate how to sort Map in Java on key and values.
 * Map can be sort on keys or values.
 *
 * @author Javin Paul
 */

public class MapSortingExample {

 
    public static void main(String args[]) {
 
        //creating Hashtable for sorting
        Map<String, Integer> olympic2012 = new HashMap<String, Integer>();
     
        olympic2012.put("England", 3);
        olympic2012.put("USA", 1);
        olympic2012.put("China", 2);
        olympic2012.put("Russia", 4);
        //olympic2012.put("Australia", 4); //adding duplicate value
     
        //printing hashtable without sorting
        System.out.println("Unsorted Map in Java : " + olympic2012);
     
        //sorting Map e.g. HashMap, Hashtable by keys in Java
        Map<String, Integer> sorted = sortByKeys(olympic2012);
        System.out.println("Sorted Map in Java by key: " + sorted);
     
     
        //sorting Map like Hashtable and HashMap by values in Java
        sorted = sortByValues(olympic2012);
        System.out.println("Sorted Map in Java by values: " + sorted);
     
     
        //Sorting Map in Java by keys using TreeMap
        Map<String, Integer> sortedMapByKeys = new TreeMap<String,Integer>();
        sortedMapByKeys.putAll(olympic2012);
        System.out.println("Sorted Map in Java by key using TreeMap : " + sortedMapByKeys);
 
     
        //Sorting Map by keys in Java using Google Collections (Guava)
        //Main benefit is you can specify any ordering like natural or toString or arbitrary
        Map<String, Integer> sortingUsingGuava = Maps.newTreeMap(Ordering.natural());
        sortingUsingGuava.putAll(olympic2012);
        System.out.println("Example to sort Map in Java using Guava : " + sortingUsingGuava);
     
     

    }
 
    /*
     * Paramterized method to sort Map e.g. HashMap or Hashtable in Java
     * throw NullPointerException if Map contains null key
     */

    public static <K extends Comparable,V extends Comparable> Map<K,V> sortByKeys(Map<K,V> map){
        List<K> keys = new LinkedList<K>(map.keySet());
        Collections.sort(keys);
     
        //LinkedHashMap will keep the keys in the order they are inserted
        //which is currently sorted on natural ordering
        Map<K,V> sortedMap = new LinkedHashMap<K,V>();
        for(K key: keys){
            sortedMap.put(key, map.get(key));
        }
     
        return sortedMap;
    }
 
    /*
     * Java method to sort Map in Java by value e.g. HashMap or Hashtable
     * throw NullPointerException if Map contains null values
     * It also sort values even if they are duplicates
     */

    public static <K extends Comparable,V extends Comparable> Map<K,V> sortByValues(Map<K,V> map){
        List<Map.Entry<K,V>> entries = new LinkedList<Map.Entry<K,V>>(map.entrySet());
     
        Collections.sort(entries, new Comparator<Map.Entry<K,V>>() {

            @Override
            public int compare(Entry<K, V> o1, Entry<K, V> o2) {
                return o1.getValue().compareTo(o2.getValue());
            }
        });
     
        //LinkedHashMap will keep the keys in the order they are inserted
        //which is currently sorted on natural ordering
        Map<K,V> sortedMap = new LinkedHashMap<K,V>();
     
        for(Map.Entry<K,V> entry: entries){
            sortedMap.put(entry.getKey(), entry.getValue());
        }
     
        return sortedMap;
    }

}

Output
Unsorted Map in Java : {USA=1, England=3, Russia=4, China=2}
Sorted Map in Java by key: {China=2, England=3, Russia=4, USA=1}
Sorted Map in Java by values: {USA=1, China=2, England=3, Russia=4}
Sorted Map in Java by key using TreeMap : {China=2, England=3, Russia=4, USA=1}
Example to sort Map in Java using Guava : {China=2, England=3, Russia=4, USA=1}


That's all on How to sort Map in Java like HashMap, Hashtable based upon keys and values. Just remember that sorting Map based upon values is more difficult than sorting Map based upon keys because values in Map can be eitehr null or duplicates which is not the case with keys.

Other Java Collection tutorials from Javarevisited

2 comments :

Anonymous said...

When we sort HashMap by values, does it retain duplicates or they lost during sorting operation ?

Anonymous said...

Why can't you use the SortedMap Interface provided by the API?

Post a Comment