How HashMap works in Java

This is very important question in core java interviews. This question is mostly asked to check if you have a very good knowledge of datastructure and internal implementations. I will try to explain HashMap internal working very simply steps-by-step.

HashMap stores the data in key-value pairs. HashMap provides us a lot of methods but in this particular post we will only discuss about put(key, value) to store data and get(key) to retrieve data methods and their internal working. HashMap works on the basis of hashing technique where bucket location address to store the element if identified using Hash value of the key object.

Datastructure Used in HashMap implementation

HashMap implemented using Array and LinkedList data structures till Java7. In Java8 LinkedList was replaced with Tree to improve the performance.

How HashMap Put(key, value) Method Works

When we call the put(key, value) method of HashMap, following process is followed.

• When put method is called, first it checks for the null key. If key is null it selects the 0 index bucket by default, create a Map.Entry object which contains both key and value and store it in the selected index.
• If key is not null, It retrieve the hashCode value of key by calling hashCode() function of key object. Now It again calls HashMaps internal hash(hashCode) function to create final hash value to find out the bucket location.
• Now as we know same hashCode can be return by two different objects. So two different keys can identify the same bucket location to store values. This is called collision and to handle with this collision situation HashMap creates a LinkedList in bucket and store all the value for same hashCode  in the LinkedList. 
• Now as we discussed earlier that HashMap uses LinkedList to store values. Threre will be a LinkedList in each bucket. So finally it creates a Map.Entry object which contains key and value both and add it to the LinkedList. 
• Finally it returns the previous value associated with the key or null.

How HashMap get(key) Method Works

When we call the get(key) method of HashMap, following process is followed.

• When get(key) method is called, first it checks for the null key. It return the value from index 0.
• If key is not null It will perform the same hashing as put(key, value) method and get the same hashCode which will identify the same bucket location.
• Now here it will get a LinkedList which contains Map.Entry object with key and value both. It will perform a linear search on LinkedList and match the key using equals() method of key object.
• Finally returns the values.

Can We Use Custom Object as HashMap Key

We can use our custom object as HashMap key, but few things to remember before choosing a key for HashMap.

• hashCode() and equals() methods should be implemented in a proper way in a HashMap key class. Because poor hashCode method implementation can cause to performance degrade. If hashCode return same value for different objects then in HashMap it will always identify the same bucket location to insert value and all values will be stores in single LinkedList. That makes the search linear and slow. 

What is Collision and How it is handled in HashMap 

As discussed earlier in this post if two different keys are returning same hashCode, then HashMap will identify the same bucket location for both entries. This is called collision.

Collision is handled by using a LinkedList in HashMap implementation. Whrere a LinkedList will be created in bucket and all entries with same hashCode will be inserted in the LinkedList.

Java8 - Changes in HashMap Implementation 

In Java8 LinkedList is replaces with BinaryTree, because in worst case scenario where hashCode() method implementation is very poor for key object LinkedList performance will degrade to O(N) while in case of BinaryTree worst case will be O(log N). 

This is all about how HashMap works in Java. If you have any doubts Please put in the comments. I will try to resolve ASAP.

Check below links also-
Bubble Sort Algorithm analysis and implementation in Java
Linear Search Algorithm analysis and implementation in Java
Binary Search Algorithm analysis and implementation in Java
Java8 - Lambda Expressions in Java
Java8 - Default and static methods in Interface
How to create Immutable classes in JAVA