Sunday, 28 June 2015

How to Sort HashMap Based On Values in Java?

     HashMap is a data structure used to store "Key" and "Value" pairs. Unlike, Arrays, ArrayLists, and LinkedLists, It doesn't preserve order of elements in which they have inserted.

So, sorting HashMap based on keys, or values is a tough interview question, if you don't know how to solve. Let's see how to solve the problem.

1. HashMap stores each key and value pair as an Entry<K,V> object. for example, given a hashmap,
 Map<String,Integer> aMap = new HashMap<String,Integer>();

for every insertion of key, value pair into the hash map, there exists one Entry<K,V> object. By making use of this Entry<K,V> object, we can sort the hashmap based on values.

2. Create a simple HashMap and insert some key and values.
Map<String,Integer> aMap = new HashMap<String,Integer>();
        
        // adding keys and values
        aMap.put("Five", 5);
        aMap.put("Seven", 7);
        aMap.put("Eight", 8);
        aMap.put("One",1);
        aMap.put("Two",2);
        aMap.put("Three", 3);

3.Retrieve the entry set from HashMap like below.
Set<Entry<String,Integer>> mapEntries = aMap.entrySet();

4. Create a LinkedList from the above mapEntries. We are going to sort this linked list, to solve our problem. We are using linked list for this purpose, because insertion of elements in linked list is faster than an array list.
 List<Entry<String,Integer>> aList = new LinkedList<Entry<String,Integer>>(mapEntries);

5. Sort the linked list using Collections.sort() method, by passing linkedlist and a custom comparator.
Collections.sort(aList, new Comparator<Entry<String,Integer>>() {


            @Override

            public int compare(Entry<String, Integer> ele1,

                    Entry<String, Integer> ele2) {

               

                return ele1.getValue().compareTo(ele2.getValue());

            }

        });

6. Using the custom comparator, we are sorting the linked list, based on the values(Entry.getValue()) of entries.
7. ele1.getValue().compareTo(ele2.getValue()) - compares the two values and returns 0 - if the two values are exactly same, 1 - if the 1st value is greater than 2nd value and -1 - if the 1st value is less than the 2nd value.
8. Collections.sort() is a built in method, which sorts the List of values only. It is overloaded in Collections class. The two methods are
public static <T extends Comparable<? super T>> void sort(List<T> list)

public static <T> void sort(List<T> list, Comparator<? super T> c)

9.Now you have sorted the linked list, and we need to store the key, value pairs into the new Map. As HashMap doesn't preserve the order, so use LinkedHashMap for this purpose.

    // Storing the list into Linked HashMap to preserve the order of insertion. 
        Map<String,Integer> aMap2 = new LinkedHashMap<String, Integer>();
        for(Entry<String,Integer> entry: aList) {
            aMap2.put(entry.getKey(), entry.getValue());
        }

10.The Complete Code is below.
package com.speakingcs.maps;

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.Set;

public class SortMapByValues {
    
    
    public static void main(String[] args) {
        
        Map<String,Integer> aMap = new HashMap<String,Integer>();
        
        // adding keys and values
        aMap.put("Five", 5);
        aMap.put("Seven", 7);
        aMap.put("Eight", 8);
        aMap.put("One",1);
        aMap.put("Two",2);
        aMap.put("Three", 3);
        
        sortMapByValues(aMap);
        
    }

    private static void sortMapByValues(Map<String, Integer> aMap) {
        
        Set<Entry<String,Integer>> mapEntries = aMap.entrySet();
        
        System.out.println("Values and Keys before sorting ");
        for(Entry<String,Integer> entry : mapEntries) {
            System.out.println(entry.getValue() + " - "+ entry.getKey());
        }
        
        // used linked list to sort, because insertion of elements in linked list is faster than an array list. 
        List<Entry<String,Integer>> aList = new LinkedList<Entry<String,Integer>>(mapEntries);

        // sorting the List
        Collections.sort(aList, new Comparator<Entry<String,Integer>>() {

            @Override
            public int compare(Entry<String, Integer> ele1,
                    Entry<String, Integer> ele2) {
                
                return ele1.getValue().compareTo(ele2.getValue());
            }
        });
        
        // Storing the list into Linked HashMap to preserve the order of insertion. 
        Map<String,Integer> aMap2 = new LinkedHashMap<String, Integer>();
        for(Entry<String,Integer> entry: aList) {
            aMap2.put(entry.getKey(), entry.getValue());
        }
        
        // printing values after soring of map
        System.out.println("Value " + " - " + "Key");
        for(Entry<String,Integer> entry : aMap2.entrySet()) {
            System.out.println(entry.getValue() + " - " + entry.getKey());
        }
        
    }
}



0 comments:

Post a Comment

Note: only a member of this blog may post a comment.