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.
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 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.
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.
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}
map.put(“abc” , 50); { hash = 344 (lets say) , index = 5 , key =”abc” , value =50 , next = null}
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
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.
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.
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.
