Understanding the Internal Working of HashMap

Internal Working of HashMap in Java

One of the most asked question in Java technical interview is How HashMap works internally ?

This blog will answer all related questions listed below :

  • What is the internal working of HashMap in Java?
  • How does a hash table work internally?
  • How HashMap works internally step by step?
  • How does HashMap resolve collision?
  • and few more…

Introduction :

HashMap is a collection in Java which implements Map interface and allows to store key-value pair.

HashMap<K,V> map = new HashMap<>();

K represent Key ,V represent Value

import java.util.HashMap;

public class Technoname {
    public static void main(String[] args) {
        HashMap<Integer,String> map = new HashMap<>();
    }
}

Above example shows declaration of HashMap with having key as Integer type and value as String type.

HashMap Operations :

  • To insert key value pairs in HashMap we use “put” method :
map.put(1, "abc");
map.put(2 , "def");
  • To get value from HashMap we use “get” method :
map.get(1);  // give "abc" as output

Similarly you can use multiple predefined methods available which can be use as per our requirements.

HashMap Operations

Internal Working of HashMap :

We insert a key-value pair into a HashMap using the map.put(key, value) command, which creates buckets of size 16 (the default size).

HashMap ArrayList Bucket
HashMap Bucket

The four objects in each node of a bucket are : { Hashcode, Key, Value, and Next }.

Each node uses Linked List data structure to maintain four objects.

  • Hashcode : The hashCode method retrieves the hash code of an object by calling hashCode(key). The hashCode() method of the Object class returns the memory reference of an object as an integer. 
  • Key : Key in HashMap object.
  • Value : Value in HashMap object.
  • Next : it is next pointer which contains address of next linked list.

Example :

1. map.put(“abc”,40) :

hash = hashcode(key) = hashcode(abc) = 344 (lets say , it will be calculated internally)

index = hash & (n-1) = 4 (lets say) // calculated using this formula

next = it will null as no other elements are there at same index

From here we got to know that at fourth index of bucket , our key and value will be stored.

HashMap Insertion Operation
Insertion in HashMap

2. map.put(“def”,55) :

hash = hashcode(key) = hashcode(def) = 512 (lets say , it will be calculated internally)

index = hash & (n-1) = 14 (lets say) // calculated using this formula

next = it will null as no other elements are there at same index

From here we got to know that at fourth index of bucket , our key and value will be stored.

HashMap Insertion Operation with multiple key value pairs
Insertion multiple key value pair in HashMap

HashMap Collision :

When calculating a hash, if the resulting value already exists in the bucket, the index will also be the same, leading to a collision in the HashMap.

Now we have two cases here :

1. When keys are same :

It is the case when we get

  • same hash value
  • same index
  • and same key at that index

So in this case at that index , the old value will be replaced by new value.

Example :

map.put(“abc” , 40) ; { hash = 344 (lets say) , index = 5 , key =”abc” , value = 40 , next = null}

HashMap Bucket LinkedList

map.put(“abc” , 50); { hash = 344 (lets say) , index = 5 , key =”abc” , value =50 , next = null}

HashMap Bucket LinkedList

Above shows the hash collision due to which the value 40 gets replaced by 50 .

2. When keys are different :

It is the case when we get

  • different hash value
  • same index
  • but different key at that index

In this case as we get different keys at same index so a new Linked List will be created at same index.

Example :

map.put(“ABC” , 65); { hash : 112 (lets say) ,index = 6, key = “ABC”, value = 65 , next = address of next linked list}

map.put(“CAB” , 11); { hash : 343 (lets say) , index = 6 , key = “CAB”, value = 11 , next = null}

HashMap Collision
HashMap Collision

Some important questions :

1. Why hash maps in Java 8 use binary tree instead of linked list ?

In case of collision, entries are stored inside the bucket in form of linked list.

As searching in linked list is of O(n) time complexity, implementation of HashMap from Java 8 onwards is changed to convert from linked list to balanced binary search tree and vice versa in case number of elements inside a bucket is above or below a certain threshold.

Searching in balanced binary search tree is of O(logn) time complexity which gives better performance over linked list in case number of elements are more.

2. What is load factor and threshold in HashMap ?

By default, the load factor is 0.75, indicating that when the size of the map reaches 75%, the bucket size doubles.

As we know that size of bucket is 16, therefore,

Threshold = size of bucket * load factor = 16*0.75 = 12

The threshold value of 12 means that when a bucket reaches 12 entries, its size doubles to 24, and so on.

3. What happen when we insert null key in Hashmap ?

If we insert null key , map.put(null , 123); then its value will be stored at 0th index of bucket.

HashMap With Null Key

Thank you !!

By reading this article, you can enhance your knowledge and develop your programming skills. We’ve provided insightful suggestions and specific examples for understanding concept of Internal Working of HashMap

Please feel free to share any other approaches or methods you may have with us by posting a comment or emailing technonamecontact@gmail.com. Your code can be highlighted on our website.

To further improve your understanding of programming concepts please check out our Data structure and algorithms section.

If you found this article informative and helpful, please share it with your friends and colleagues. If you have any questions or feedback, please feel free to leave a comment or contact us.

Follow us on Twitter for daily updates and new content.

Leave a Reply

Your email address will not be published. Required fields are marked *