Java Collections — Internal Implementation/Working of HashMap

In this article, we will see internal working and implementation of HashMap. And also we will learn how to fetch elements using the get() method, what happens when we call the put() method for storing elements, and what is the purpose of hashing.

Before we dive into HashMap’s internal working there are a few concepts that should be cleared.

1. Hashing
2. Bucket
3. Node

Hashing — Hashing is a process of converting an object into an integer form by using the hashCode() method. Hash code represents the memory reference of the object.

Syntax — public int hashCode()

equals() — This method is used to check 2 objects are equal or not.

Syntax — public boolean equals(Object obj)

HashMap uses equals() to compare the key whether they are equal or not.

Bucket — Bucket is an array of nodes. Each node has a data structure like a linked list.

Node — Node represents data packets that store key, value, hash code, and reference of next element.

The default size of HashMap is 16 with a load factor of 0.75, which means 16*0.75=12. After reaching on 12th index it increases its size based on the below formula.

Capacity = number of buckets x load factor(0.75)

2⁴ = 16 => 16 x 0.75 = 12

2⁵ = 16 => 36 x 0.75 = 27

2⁶ = 16 => 72 x 0.75 = 54

Data Structure — Hash Table (Array and LinkedList)

Default Size — 16

Inserting Elements in HashMap

When we insert the first element then it will calculate the index for that element with the help of hashCode() and capacity.

index = hashCode(key) x (n-1)

Example — We try to insert “AaBB” as key then hashCode(“AaBB”) returns 2031744 and the index will be

index = 2031744 & (16–1) = 4 then it will go to index 4

Hash Collision

If the calculated index value is the same for two or more keys.

Example — BBBB

index = 2031744 & (16–1) = 4 (supposed)

Insert null as key

If we try to add null as a key then it will always store this element on the 0 index.

And if we try to add more than one null then it will override the previous value.

Example -

map.put(null, “value1”);

map.put(null, “value2”); // it will override previous one

If we get the same hash code and index for different elements then it will compare both of the keys with the help of equals() method and if both keys are different then it will store the second element next to the already present element.

Fetching the Elements

If we try to fetch an element then we have to pass the key to get() then the hash code of the key is calculated and we get the index.

After getting the hash code, the index will be calculated.

Iterating elements

We use Map.entrySet() that returns collection view (Set <Map.Entry<k, v>>) of the mappings contained in this map.

for (Map.Entry<String, String> entry : map.entrySet()) {

System.out.println(entry.getKey() + “ : “ + entry.getValue());

}

Note :

1. HashMap is not synchronized, but we can make it synchronize by Collections.synchronizedMap() method.
2. More than one key can return the same hash code.