HashMap is a very popular data structure used in the programming paradigm. Many programming problems in software engineering interviews can be tackled by the simple use of a HashMap.

In this article, we will cover:

• The Internal Workings of a HashMap
• Problem Statement
• Solution #1: Sorting a HashMap Using a LinkedHashMap 
• Solution #2: Sorting a HashMap Using a TreeMap
• Time and Space Complexity of Sorting a HashMap
• FAQs on Sorting a HashMap

The Internal Workings of a HashMap 

A HashMap is used to store key-value pairs. There are various use cases of a HashMap, such as:

• Checking whether a key is present or not in a HashMap
• Getting the value corresponding to a particular key if it’s present in a HashMap
• Removing a key-value pair from a HashMap

The HashMap class in Java is almost equivalent to HashTable, except for the fact that it’s unsynchronized and permits null values. Here’s what the internal workings of a HashMap looks like: 

Let’s break it down:

1. We compute the hashcode for each of the keys being inserted.

2. Using the hashcode, we check in which bucket the key is to be stored.

• In the above image, let’s assume the hashcode for IronMan is 002 — it’ll be stored in the second bucket that maintains a pointer to a List, where each node contains a key and its corresponding value.

3. Next, we check if there is a List of nodes present corresponding to the bucket. 

4. If a List is present, we create a new Node and add it to the end of the List; otherwise, we create a new list.

5. Now, we check if any key present in the entries of the List matches the key.

6. If a match is found, override the value; else, add a new entry to the List.

The behavior of a HashMap can be thought of as a caching mechanism. In caching, we're not concerned with the order of the elements. We're just concerned about the speed at which we can read an element and gain access to the value using the element (if it's present in the cache). Both read and access are O(1) operations. 

Some programming challenges involve ordering elements that are present in a HashMap. Ordering by key is easy, as Java supports TreeMap, where every key-value pair is inserted into the HashMap by the natural order of keys. 

We can also define a custom comparator and assign it to the TreeMap constructor to define our custom ordering of elements. It gets tricky when we want to order the key-value pairs of the HashMap based on values. The rest of this article is dedicated to solving this problem.

Problem Statement

We are provided a HashMap of key-value pairs, and we are required to sort this HashMap based on its values. For example, let’s say we are given a list of superheroes and their strengths. 

Now, if we sort these values based on the strength of the superheroes, we get the following result:

If two superheroes have the same strength, we arrange them based on the alphabetical order of their names and hence the above output.

We can assume the number of superheroes is at max 106, and all superhero names are unique.

Solution #1: Sorting a HashMap Using a LinkedHashMap 

In the first solution, the key idea is to store each entry of the HashMap in a list and then sort the list and finally store the list elements in a LinkedHashMap. Here’s how it works:

1. As we know, the key-value pairs stored in a HashMap do not have an order. Hence, we want to save the key-value pairs in a different data structure to sort them based on their value and maintain order.
2. So we choose an ArrayList, where each index of the list contains a key-value pair.
3. Sort the ArrayList based on values present in each key-value pair.
4. Finally, get the sorted list and convert it back to a map while maintaining its order.
   

Algorithm #1 for Sorting a HashMap

Sorting_hashMap (HashMap<Key , Value> hashmap):

Step 1: Copy the elements of hashmap into an ArrayList

Step 2: Sort the list using any sorting algorithm of choice

Step 3: Copy the list items into a LinkedHashMap

Step 4: Return the LinkedHashMap 

Step 5: Exit

Here’s what we’re doing:

First, we copy the key-value pairs present inside the HashMap into an ArrayList. We use ArrayList because it’s dynamic, and we do not need to specify the list size at the time of creation. 

Next, we sort the list and pass a custom comparator to define our way of ordering the elements. (Read on for details on how a comparator works in Java). 

Finally, we copy the elements from the sorted list into a LinkedHashMap. The advantage of LinkedHashMap is that elements can be accessed in their insertion order, and thus we return a map that will contain all key-value pairs sorted by value.

How a Comparator Works in Java

A comparator object is used for comparing two objects of a user-defined class.

Syntax: public int compare ( Object object1 , Object object2  )

The "compare” method returns three categories of values based on object comparison:

• < 0   → denotes object1 is smaller than object2
• 0    → denotes that both object1 and object2 are equal
• > 0    → denotes that object1 is greater than object2
  

Whenever we insert an element into the list, the comparator function will compare the new object inserted against the elements and decide whether to swap its position, thus maintaining the desired sorted order.

For our use case, we simply need to compare the values of the keys. But what if the values of two different keys are the same? As per the example given in the problem statement, such a scenario can definitely arise. 

We only need to tweak our compare method a bit, where we first check if two values are the same, and then, we compare them based on their keys; else, we compare them based on their values.

public int compare(Map.Entry o1, Map.Entry o2) {
               
if ( o1.getValue() == o2.getValue() )
           return o1.getKey().compareTo(o2.getKey());
else
     return Integer.compare(o1.getValue() , o2.getValue());
}

‍

 Now that our compare method is ready, let's look at the pseudocode.

Pseudocode #1 for Sorting a HashMap

sorted_HashMap( HashMap hashmap ) :
   list = []
   for( each key/value in hashmap )
list.add( key/value )
 
   sort( list , comparator )
   
   map = new LinkedHashMap<>(); 
   for ( each key/value in list )
         map.put( key , value );
 
   return map;

‍

Code #1 for Sorting a HashMap

import java.util.*;
class Main
{
   public static void main (String[] args) throws java.lang.Exception
   {
       // Creating an array of superHero names and their strengths.
       String[] superHeroes = new String[] { "CaptainAmerica" , "Thanos" , "Thor" , "IronMan" };
       Integer[] strength = new Integer[] { 50 , 100 , 75 , 50 };
      
       // Insert the superHero name and its strength as a key-value pair inside a HashMap.
       Map hashmap = new HashMap<>();
       for (int i=0 ; i < superHeroes.length ; i++) {
           hashmap.put( superHeroes[i] , strength[i] );
       }
 
       System.out.println("Values before sorting : ");
       display(hashmap);
 
       Map sortedMap = sortedHashMapByValues(hashmap);
 
       System.out.println("Values after sorting : ");
       display(sortedMap);
   }
 
   private static Map sortedHashMapByValues(Map hashmap) {
       // Create an ArrayList and insert all hashmap key-value pairs.
       ArrayList> arrayList = new ArrayList<>();
       for (Map.Entry entry : hashmap.entrySet()) {
           arrayList.add(entry);
       }
 
       // Sort the Arraylist using a custom comparator.
       Collections.sort(arrayList, new Comparator>() {
           @Override
           public int compare(Map.Entry o1, Map.Entry o2) {
               if ( o1.getValue() == o2.getValue() )
                   return o1.getKey().compareTo(o2.getKey());
 
               return Integer.compare(o1.getValue() , o2.getValue());
           }
       });
      
       // Create a LinkedHashMap.
       Map sortedMap = new LinkedHashMap<>();
      
       // Iterate over the ArrayList and insert the key-value pairs into LinkedHashMap.
       for (int i=0 ; i hashmap) {
       for( Map.Entry entry : hashmap.entrySet() ) {
           System.out.println( "Key : " + entry.getKey()+ " \t  value :  " + entry.getValue() );
       }
   }
}

‍

Solution #2: Sorting a HashMap Using a TreeMap

Here, we create a TreeMap in Java with a custom comparator that compares all key-value pairs based on their values. Then, we simply add all key-value pairs into the TreeMap.

Algorithm #2 for Sorting a HashMap

Sorting_HashMap (HashMap<Key , Value> hashmap): 

Step 1: Create a TreeMap in java with a custom comparator.

Step 2: Comparator should compare based on values and then based on the keys.

Step 3: Put all key-value pairs from the hashmap into the treemap.

Step 4: return the treemap.

Step 5: Exit

In solution 2, we first create a TreeMap with a custom comparator. 

Next, we simply insert all the key-value pairs, and our comparator takes care of inserting the values inside TreeMap based on values in ascending order. 

Finally, we return our TreeMap object.

Pseudocode #2 for Sorting a HashMap

sorted_hasmap( HashMap hashmap ) :
   Comparator comparator = new Comparator() {
      public int compare( T o1 , T o2 ) {
	    if ( hashmap.get(o1) != hashmap.get(o2) )
            return  hashmap.get(o1) - hashmap.get(o1); 
          else
     return o1.compareTo(o2);
}
   }
 
   TreeMap map = new TreeMap 
   for( each key/value in hashmap )
map.add( key/value )
 
   return map;

‍

Code #2 for Sorting a HashMap

import java.util.*;
class Main
{
  public static void main (String[] args) throws java.lang.Exception
   {
       // Creating an array of superHero names and their strengths.
       String[] superHeroes = new String[] { "CaptainAmerica" , "Thanos" , "Thor" , "IronMan" };
       Integer[] strength = new Integer[] { 50 , 100 , 75 , 50 };
 
       // Insert the superHero name and its strength as a key-value pair inside a HashMap.
       Map hashmap = new HashMap<>();
       for (int i=0 ; i < superHeroes.length ; i++) {
           hashmap.put( superHeroes[i] , strength[i] );
       }
 
       System.out.println("Values before sorting : ");
       display(hashmap);
 
       Map sortedMap = sortedHashMapByValues(hashmap);
 
       System.out.println("Values after sorting : ");
       display(sortedMap);
   }
 
   private static Map sortedHashMapByValues(Map hashmap) {
       // Insert all key-value pairs into TreeMap using a custom comparator.
       TreeMap treeMap = new TreeMap<>((o1, o2) -> {
           if ( hashmap.get(o1) != hashmap.get(o2) )
               return Integer.compare( hashmap.get(o1) , hashmap.get(o2) );
 
           return o1.compareTo(o2);
       });
 
       treeMap.putAll(hashmap);
       return treeMap;
   }
 
  public static void display(Map hashmap) {
       for( Map.Entry entry : hashmap.entrySet() ) {
           System.out.println( "Key : " + entry.getKey()+ " \t  value :  " + entry.getValue() );
       }
   }
}

‍

Output (for Both Solutions)

Values before sorting : 

Key : Thor     value :  75

Key : CaptainAmerica  value :  50

Key : Thanos     value :  100

Key : IronMan   value :  50

Values after sorting : 

Key : CaptainAmerica  value :  50

Key : IronMan   value :  50

Key : Thor     value :  75

Key : Thanos     value :  100

Time and Space Complexity of Sorting a HashMap

The complexity for both solutions is the same:

• Time complexity: O(nlogn)
• Space complexity: O(n)

Time complexity for Solution 1 is O(nlogn) because we sort the ArrayList that consists of n key-value pairs, and the presence of sorting algorithms makes the worst-case complexity O(nlogn). In addition, we store the elements in a LinkedHashMap — so the complexity becomes (nlogn + n), which is O(nlogn).

Time Complexity for Solution 2 is O(nlogn) because TreeMap is a Red-Black tree-based NavigableMap implementation. It’s known that Red-Black tree is a kind of self-balancing binary search tree, and so each insertion takes O(logn) time. Here, we have n key-value pairs, making the total complexity O(nlogn).

Space complexity is O(n) as we store the elements in a list of size n in both solutions.

FAQs on Sorting a HashMap

Question 1: While sorting a HashMap using a LinkedHashMap, why is an ArrayList preferred over an array?

Answer: If you are sorting a HashMap using a LinkedHashMap, you can choose an array instead of an ArrayList. However, the drawback of using an array is that you need to know the array size beforehand. ArrayList is dynamic, and you need not specify the size upon ArrayList creation, making it the more preferred option.

Question 2: Are comparators frequently used in sorting based on different parameters?

Answer: In general, programming interview problems require you to sort 2-D arrays, maps, or lists based on different parameters, and in such situations defining a custom comparator can be very useful.

Are You Ready to Nail Your Next Coding Interview?

If you’re looking for guidance and help with getting started, sign up for our free webinar. As pioneers in the field of technical interview preparation, we have trained thousands of engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

--------

Article contributed by Problem Setters Official