Author
Abhinav Rawat
Product Manager @ Interview Kickstart | Ex-upGrad | BITS Pilani. Working with hiring managers from top companies like Meta, Apple, Google, Amazon etc to build structured interview process BootCamps across domains
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:
A HashMap is used to store key-value pairs. There are various use cases of a HashMap, such as:
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.
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.
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.
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:
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.
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:
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<string, integer> o1, Map.Entry<string, Â Â integer> o2) {
      Â
if ( o1.getValue() == o2.getValue() )
     return o1.getKey().compareTo(o2.getKey());
else
  return Integer.compare(o1.getValue() , o2.getValue());
}
</string,></string,>â€
 Now that our compare method is ready, let’s look at the pseudocode.
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;
â€
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<string, integer> sortedMap = sortedHashMapByValues(hashmap);
   System.out.println("Values after sorting : ");
   display(sortedMap);
 }
 private static Map<string, integer> sortedHashMapByValues(Map<string, integer> hashmap) {
   // Create an ArrayList and insert all hashmap key-value pairs.
   ArrayList<map.entry> arrayList = new ArrayList<>();
   for (Map.Entry entry : hashmap.entrySet()) {
     arrayList.add(entry);
   }
   // Sort the Arraylist using a custom comparator.
   Collections.sort(arrayList, new Comparator<map.entry<string, integer>>() {
     @Override
     public int compare(Map.Entry<string, integer> o1, Map.Entry<string, integer> o2) {
       if ( o1.getValue() == o2.getValue() )
         return o1.getKey().compareTo(o2.getKey());
       return Integer.compare(o1.getValue() , o2.getValue());
     }
   });
  Â
   // Create a LinkedHashMap.
   Map<string, integer> sortedMap = new LinkedHashMap<>();
  Â
   // Iterate over the ArrayList and insert the key-value pairs into LinkedHashMap.
   for (int i=0 ; i<arraylist.size() ; i++)  sortedmap.put(arraylist.get(i).getkey() , arraylist.get(i).getvalue()); return sortedmap; } public static void display(map hashmap) {
   for( Map.Entry entry : hashmap.entrySet() ) {
     System.out.println( "Key : " + entry.getKey()+ " t  value :  " + entry.getValue() );
   }
 }
}
</arraylist.size()></string,></string,></string,></map.entry<string,></map.entry</string,></string,></string,>â€
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.
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.
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;
â€
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<string, integer> sortedMap = sortedHashMapByValues(hashmap);
   System.out.println("Values after sorting : ");
   display(sortedMap);
 }
 private static Map<string, integer> sortedHashMapByValues(Map<string, integer> 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() );
   }
 }
}
</string,></string,></string,>â€
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
The complexity for both solutions is the same:
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.
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.
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!
——–
Article contributed by Problem Setters Official
Time Zone:
Get your enrollment process started by registering for a Pre-enrollment Webinar with one of our Founders.
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
Just drop your name and email so we can send your Power Patterns PDF straight to your inbox. No Spam!
By sharing your contact details, you agree to our privacy policy.
Time Zone: Asia/Dhaka
We’ve sent the Power Patterns PDF to your inbox — it should arrive in the next 30 seconds.
📩 Can’t find it? Check your promotions or spam folder — and mark us as safe so you don’t miss future insights.
We’re hosting a private session where FAANG insiders walk through how they actually use these Power Patterns to crack interviews — and what sets top performers apart.
🎯 If you liked the PDF, you’ll love what we’re sharing next.
Time Zone:
