Java: Working of HashMap

Hi Guys,

One of most important question about Collection is What is the internal working of HashMap.

Lets start with a life example. You have been given a task to collect paper pieces with number on it and asked to organize it. So first thing which strike you to store them in some bucket.

Now your supervisor comes and ask you to check whether number 87 exists or not. You start searching for the number in the bucket one by one and finally you find that it is not there. In other case you are asked to check number 90, you have to perform same task what you have done with number 87. And finally you find the number. This is a tedious task when number of pieces increase. Now it is the time when you have to think something different to organize them properly.

You can come with the approach of adding some more bucket but this time add some algorithm to organize pieces properly.
Initially you have decided to keep four buckets and with some algorithm you will place each paper pieces in respective buckets.
You have created an algorithm lets say you applied modulus approach
number to the modulus of 4.
e.g
12%4 = 0 [Bucket 0]
9%4 = 1 [Bucket 1]
90%4 = 2 [Bucket 2]
77 % 4 = 1  [Bucket 1]
7 % 4 = 3 [Bucket 3]
and so on

Now it become easy to organize pieces in 4 different buckets.

At one time when number of pieces in each bucket increases above limit, so you will add some more buckets and using above algorithm you will place each pieces in respective bucket. 

Again your supervisor ask you to search for number 27 . You just have to apply your algorithm and find bucket number 27 % 4 = 3 i.e bucket number 3. Now you know that your number 27 exists in bucket 3 you will have to check with pieces in the bucket and checks which number match with number 27.

HashMap working

In HashMap key and value should be of Object type instead of primitive data type.
When HashMap is initialize default capacity is defined i.e number of buckets and capacity of each bucket content. This calculation is done using class hashCode function. The load factor monitors how full each bucket is until its size increase and then rehash the bucket.

a. Put value in HashMap

Map<String, Integer> hashMap = new HashMap<String, Integer>();
hashMap.put("One", 1);
hashMap.put("Two", 2);
hashMap.put("Three", 3);

b. Get value from HashMap

hashMap.get("Three");

HashMap gets key hashcode and search for bucket and then uses equals method to verify key.
From above example
We have to get value for object "Three". Firstly it get hashcode i.e 001 then search for bucket in which 001 is found. When it gets the bucket it uses equals method to verify key and return its value.

Note: Both equals and hashcode method should be properly handled or you will get unexpected result.

Scenario 1:  Where two different key has same hashcode.
Here key "One" and "Two" has same hashcode.  So while searching for key "Two" HashMap performs similar task to search for bucket i.e using hashcode to find correct bucket. The bucket has more than one object so it will traverse each of them and match its key using equals method.
Note: In HashMap value is stored in linked list.

Scenario 2: Where two same key has same hashcode.
If key needs to be inserted and already inserted hashkey's hashcodes are same, and keys are also same(via reference or using equals() method) then override the previous key value pair with the current key value pair.

Performance of HashMap

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor.

The capacity is the number of buckets in the hash table( HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.), and the initial capacity is simply the capacity at the time the hash table is created.


The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

In HashMap class, the default value of load factor is (.75) .

I hope this brief description helped you to understand how hashmap works.

Good Day :)