Internal implementation of HashMap

Internal implementation of HashMap

This is one of the most commonly asked interview questions, “What is the Internal implementation of HashMap” OR “What are the data structures used in HashMap” OR “How HashMap maintains the uniqueness of keys”. In this tutorial, we will get answers for all these questions. 

I have added the code snippets from HashMap.class file which is decompiled using jadclipe plugin. Check this blog for details.

Map Interface

First of all, lets see what does Map interface contains. Map interface has a inner interface named Entry which has following method definition.

As you can see, Map.Entry interface and five methods that needs to be implemented.

Map Implementation in HashMap

Lets have a look at HashMap class. In HashMap class, there is a static inner class named as “Entry” which implements the Map.Entry interface available in Map interface. Since HashMap implements Map, Map.Entry interface is also available for HashMap to implement its methods. Below code snippet shows the implementation of Map.Entry interface in a Entry class.

You can see, all the five methods are being implemented in the Entry class. There are three properties in this inner class – “key” and “value” of type Object, “next” of type Entry and “hash” of type int. Whenever new Entry object is created it consists for above four properties. Entry object is created via constructor –

Whenever a HashMap object is created, it consists of an Array of Entry (Entry[]) and the variable name is “table”. Below is the snippet of declaration in HashMap class.

By default, the HashMap object is created with the threshold value of 16 and with load-factor value of 0.75F. Please note, you can specify this value while creating hash map object. Below is the code snippet –

This internally calls the HashMap constructor with two parameters-

You can see a table variable is initialized. Now lets see how does HashMap adds the element in it.

As you can see in above implementation, Key and Value are passed as the parameters to “put” method, out of these only key is processed and it is compared with all the other keys in the table, see the for loop in the above code.

Before processing on key and values, hash code and index position is identified for the key value pair. Below are the methods for same-

After identifying hashcode and index position the keys’ hashcode are compared and then the contents of keys’ are checked and “NO VALUES ARE COMPARED HERE“. If the key is null then it will send for processing at top, if the key is not null and no same key is present in the table array then it will add that key value pair in the table[]. See the below implementation of addEntry method which internally calls a createEntry method.

For each key value pair a Entry object will be created and same will be added in table[] at specified location. Here specified location is the index position calculated in put method and along with key value data, hashcode is also passed to this method which will be set in the Entry object created for this new entry. Once the Entry object is created for new key and value pair, it will be added in the table[] and null will be returned from put method.

If the key is already present in the table[] then the value corresponding to that specific Entry will be updated with the new value and old value will be returned from put method. In this case new element is not added in the table[].

Lets see the simple example in debug mode and step wise execution of the flow. I have added step wise screenshot for each insertion of element in the hashmap. Take a loot at the “retValue” variable which will return the previous value if the key is already present else will return null in case the key is added for first time.

Run the program in debug mode and go further pressing “F6”. You will see outputs like –

first entry - Internal implementation of hashmap

first entry

For the first time, new entry is created and is inserted in table. Since this is new key, retValue is null.

second entry - internal implementation of hashmap

second entry

Second entry is also new, so it is added in table[] and now the length of table[] becomes 2.

third entry - internal implementation of hashmap

third entry

Third entry contains the key that was already present in the table, so the value is modified and previous value is returned. Check the index position and the hashcode for this entry it is same that of first entry. The only change is in the value and everything else is same. Refer below screens for similar details.

fourth entry - internal implementation of hashmap

fourth entry

fifth entry - internal implementation of hashmap

fifth entry

sixth entry - internal implementation of hashmap

sixth entry

seventh entry - internal implementation of hashmap

seventh entry

In the remaining entries only value is changed and key, hashcode and index position remains same. This is internal implementation of hashmap and its working. Hope this will help.

Regards,

Nikhil Naoghare.

Leave a Comment

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