Is HashMap the solution to every problem? Let’s figure out!

We think that the only solution to almost every coding problem, especially a Leetcode problem—HashMap—is the collective favourite data structure for all.

But, do you know what makes it so popular, and is it actually the problem-solver in every case?

Lets see.

Before we talk about hashmaps, let’s first learn about the two main parts of a hashmap: the hash and the map.

In the context of hashmaps, “hash” refers to the process of applying a hash function to a key to determine the index or location where the corresponding value should be stored or retrieved within the underlying data structure.

Hash Function: A function that takes an input (in this case, the key) and produces a fixed-size string of bytes, typically of a fixed length. The output of this function is often referred to as the “hash value” or “hash code.”

A “map” is an abstract data type that stores key-value pairs and allows for efficient lookup, insertion, and deletion of elements based on their keys. The Map interface in Java represents a collection of key-value pairs, where each unique key maps to a specific value.

When combined, the “hash” part of a HashMap is responsible for efficiently organizing and locating data within the underlying data structure, while the “map” part provides the interface for associating keys with values and performing operations on them.

In Java , the Map interface and hashing come together to form our favourite data structures: HashMap.

But in this article, we are not just going to talk about HashMaps. We also want to discuss about 2 other Map implementations — LinkedHashMap and ConcurrentHashMap.

In this article, these are the major takeaways for you:

Features of HashMap

Hashmap internals

10 most common coding questions

Limitations of hashmap

Concurrent HashMap vs Collections.synchronizedMap()

ConcurrentHashMap internals

Linked HashMap internals

Interview Questions on ConcurrentHashMap

Interview Questions on LinkedHashMap

Interview Questions on Hashmap

What are HashMaps?

HashMap provides the basic implementation of Map interface in Java. It is a data structure which stores the data in key-value pairs, where every key is mapped to a value.

You can think of it as a dictionary where you can look up a word (key) and find its corresponding definition (value). Now, you might be wondering, where does hashing come into use?

Behind the scenes, HashMaps use hashing to quickly locate the value associated with a given key. This gives it the power of O(1) time complexity.

Here are some important features of hashmap that you must know:

1. Data is stored in key-value pairs.

2. Uses hashing to store and retrieve data.

3. Each key must be unique.

4. It can dynamically resize itself as required to accommodate more key-value pairs.

5. Allows null values and only one null key.

Now that you’re familiar with so many features of HashMap, you might be curious about how HashMaps actually accomplish all of this internally.

Let’s break down how HashMaps have O(1) time complexity

A HashMap internally uses an array of linked lists or a balanced tree (depending on the implementation) to store key-value pairs

When you insert a key-value pair into a HashMap, the key is hashed to determine the index in the underlying array where the value will be stored.

The hashing function converts the key into an integer value, which serves as the index for storing the value in the array.

Ideally, a good hashing function distributes the keys evenly across the array, minimizing collisions (i.e., multiple keys hashing to the same index).

In the ideal case where there are no collisions, accessing an element in the HashMap involves calculating the hash code of the key and directly accessing the corresponding index in the array.

This operation has constant time complexity, regardless of the size of the HashMap.

To understand more about how HashMaps work internally, what are collisions, collision resolution strategy, Java 8 changes, load factor etc, you can watch my YouTube video, where I discuss the internal working of HashMaps in detail.

Although HashMaps are quite powerful, it comes with its own set of limitations. For now, we will discuss two major disadvantages of hashmaps and their possible solutions available.

1. HashMap is unsynchronized; hence they not thread-safe. When multiple threads try to modify a HashMap simultaneously, it leads to ConcurrentModificationException, where one thread modifies the structure of the HashMap while another thread is iterating over it. It may also lead to race conditions.

This code will throw ConcurrentModificationException:

2. They are unordered; the order in which elements are stored and retrieved may not be the same.

Output:

Top 9 Most Commonly Used Coding Questions on HashMap:

1. Create a copy of a HashMap.

2. Check if a HashMap is empty or not.

3. Check if two HashMaps contain the same key-value pairs.

4. Find the key with the maximum value in a HashMap.

5. Remove duplicate values from a HashMap.

6. Merge two HashMaps while keeping the values of common keys intact.

7. Remove all null values from a HashMap.

8. Find the frequency of each word in a HashMap.

9. Sort a HashMap based on its values.

As we already discussed, there are two major limitations of HashMap, one is no thread-safety, and the other is no ordering. Now that we have some idea about HashMap and some of its most commonly used built-in functions, we will now look into how we can overcome these limitations. Let’s start with the Concurrency problem. There can be possible ways to solve it:

1. Using Concurrent HashMap
2. Using Collections.synchronizedMap()

What is ConcurrentHashMap?

ConcurrentHashMap is a thread-safe implementation of the Map interface, providing concurrent access to key-value pairs without explicit synchronization. It can be thought of as a thread-safe version of HashMap.

Some important features of ConcurrentHashMap are as follows:

1. It is thread-safe; allows multiple threads to access and modify it concurrently without external synchronization.

2. Does not allow null objects in key or value.

3. Follows bucket locking mechanism: Multiple threads can concurrently perform read operations on the object. However, to perform write operation , thread must acquire a lock on the specific segment it intends to operate on.

Now, to learn how ConcurrentHashMap ensures thread safety and allows concurrent programming, you can watch my detailed YouTube video on the internal working of ConcurrentHashMap.

As discussed, we can also use Collections.synchronizedMap()to synchronize the HashMap.

Collections.synchronizedMap() is a method provided by java.util.Collections which returns a synchronized implementation of HashMap.

Difference Between Collections.synchronizedMap() and Concurrent HashMap

Now, coming to the second limitation of HashMap, which is unpredictable iteration order. This can be solved by using LinkedHashMap.

What is LinkedHashMap?

LinkedHashMap is another class declared in Java’s Collections framework which extends the functionality of HashMap by maintaining an iteration order of its elements. Here, elements are stored in the order of their insertion and can be accessed in the order of their insertion as well as their access order.

Some important features of LinkedHashMap are as follows:

1. Preserves the order of element insertion. Elements are retrieved in the same order they were added.

2. Provides an option for access order; most recently accessed element is placed at the end of the iteration order.

3. It may have one null key and multiple null values.

4. Does not allow duplicate keys.

5. It is non-synchronized.

To learn more about LinkedHashMap and its internal working, you can watch my YouTube video linked below:

Hoping you have also watched the Youtube videos suggested above, now you can try to attempt the below interview questions on all 3 types.

Interview Questions on HashMap:

1. State the differences between a Hashmap and a Hashtable in Java.
2. What happens when you try to store duplicate keys in a hashmap?
3. What is the order in which keys are stored in a hashmap?
4. What is collision in HashMap? How can we handle it?
5. What factors determine the performance of a hashmap?
6. What is the significance of hashCode() and equals() methods in HashMap keys?

Interview Questions on ConcurrentHashMap:

1. Can multiple threads read from ConcurrentHashMap same time?
2. Can one thread read and the other writes on ConcurrentHashMap at the same time?
3. What do you mean by concurrency level in ConcurrentHashMap?
4. Is the Iterator of ConcurrentHashMap fail-safe or fail-fast?
5. What will happen if you add a new mapping in ConcurrentHashMap while one thread is iterating over it?

Interview Questions on LinkedHashMap:

1. How does the performance of LinkedHashMap compare to a regular HashMap?
2. How does LinkedHashMap handle concurrency?
3. When would using a LinkedHashMap be useful over a HashMap?
4. What is the performance impact of using LinkedHashMap compared to HashMap?

That’s all for this article.

Thanks for reading.

If you liked this article, please click the “clap” button 👏 a few times.

It gives me enough motivation to put out more content like this. Please share it with a friend who you think this article might help.

Connect with me — Varsha Das | LinkedIn

If you’re seeking personalized guidance in software engineering, career development, core Java, Systems design, or interview preparation, let’s connect here.

Rest assured, I’m not just committed; I pour my heart and soul into every interaction. I have a genuine passion for decoding complex problems, offering customised solutions, and connecting with individuals from diverse backgrounds.

Follow my Youtube channel — Code With Ease — By Varsha, where we discuss Java & Data Structures & Algorithms and so much more.

Subscribe here to receive alerts whenever I publish an article.

Happy learning and growing together.