How HashMap Works Internally in Java

In this article, we are going to see how HashMap internally works in JAVA. Also, we will have a look at what Java 8 made changes to the internal working of Hashmap to make it faster. 

A HashMap is a map used to store mappings of key-value pairs. To learn more about the HashMap, visit this article: HashMap in Java.

HashMap in Java works on hashing principles. It is a data structure which allows us to store object and retrieve it in constant time O(1) provided we know the key. In hashing, hash functions are used to link key and value in HashMap.

How Hashmap Calculates the Index of a Bucket in Java

To understand how HashMap works internally in Java, we must know about how the HashMap calculates the index of the bucket. Until now, we know the internal structure of HashMap, that HashMap maintains an array of the bucket. But when we store or retrieve any key-value pair, HashMap calculates the index of the bucket for each and every operation. The Key object is used to calculate the index of the bucket. By using this key, the hash value is calculated using the  hash(key) private method of HashMap.

Note:  hash(key) the method is a private method of HashMap that returns the hash value of the key, also if the hash value is too large then converts it into a smaller hash value.

But what will happen, if the hash value of Key Object returns the integer that is greater than the size of the array i.e., hash(key) > n, then  ArrayOutOfBoundsException could be raised. To handle this situation, HashMap reduces the hash value between 0 and n-1 using an expression :

Index Calculating Expression:

index = hash(key) & (n-1)

Now, this index value is generated is used by HashMap to find bucket location and can never generate any Exception as the index value always from 0 to n-1.

What put() Method Does

Let’s note down the internal working of put method in hashmap.

First of all, the key object is checked for null. 

If the key is null, the value is stored in  table[0] position, because hashcode for null is always 0.

Then on the next step, a hash value is calculated using the key’s hash code by calling its hashCode()  method. This hash value is used to calculate the index in the array for storing the Entry objects. JDK designers well assumed that there might be some poorly written  hashCode() functions that can return very high or low hash code value. To solve this issue, they introduced another hash() function and passed the object’s hash code to this hash() function to bring hash value in the range of array index size.

Now the indexFor(hash, table.length) the function is called to calculate the exact index position for storing the Entry object.

How Collisions Are Resolved

Here comes the main part. Now, as we know that two unequal objects can have the same hash code value, how two different objects will be stored in the same array location called a bucket.

The answer is LinkedList. If you remember, the Entry class had an attribute "next." This attribute always points to the next object in the chain. This is exactly the behavior of the LinkedList.

So, in case of collision, Entry objects are stored in a linked list form. When an Entry object needs to be stored in a particular index, HashMap checks whether there is already an entry. If there is no entry already present, the entry object is stored in this location.

If there is already an object sitting on a calculated index, its next attribute is checked. If it is null, and the current entry object becomes the next node in LinkedList. If the next variable is not null, the procedure is followed until the next is evaluated as null.

What if we add another value object with the same key as entered before? Logically, it should replace the old value. How it is done? Well, after determining the index position of the Entry object, while iterating over LinkedListd on the calculated index, HashMap calls equals method on the key object for each entry object.

All these entry objects in LinkedList will have similar hashcode but  equals()  method will test for true equality. If key.equals(k) will be true then both keys are treated as the same key object. This will cause the replacement of value objects inside the entry object only.

Visit the original article.