How HashMap works – Its internal implementation

HashMap is one of the most commonly used collections in Java. Using it is pretty easy but understanding its implementation can get  a little complicated. Here is a simple example which we will use to explain its implementation

1
2
3
4
5
6
Map<String, String> map = new HashMap<String, String>();
		map.put("ab", "value-a");
		map.put("cd", "value-c");
		map.put("ef", "value-e");
		map.put("abcdef", "value-f");
		map.put("ab", "value-a-new");

Lets take first line map.put(“ab”, “value-a”). It calls the put() method of HashMap class

Inside this first hash(key) method will be called which will calculate the hash of the key

Hash() function calls hashcode function of the key. As key is of type String, this is the hashcode method of String class. Just for your information decimal values of characters ‘a’ and ‘b’ are 97 and 98 respectively

h = (31*0 + 97)

h = 31(31*0 +97) + 98

h = 3105

So hashcode of the given key(“ab”) is 3105

Now we enter the main method putVal(). Here ‘table’ is the main data structure which will be null right now. resize() will initialize the table size with default initial capacity of 16

(n – 1) & hash limits the hashcode value to some value which is less than n. As hashcode is 3105 but we have only 16 buckets, so we will convert it into a number which is less than 16

So it will be : (16 -1) & 3105 = 1. 

So it will go to first bucket. But as this bucket is new and still not created, a new node will be created :

tab[i] = newNode(hash, key, value, null);

New node consists of current key, its value, hash of the key and next node it points to which will be null right now

So now basically we have inserted the first node.

Not lets jump to second line of our sample code map.put(“cd”, “value-c”);

hash() of string “cd” comes out to be 3169

And bucket number is :(16 -1) & 3169 = 1
So this will also go to bucket number 1. But this time bucket 1 is not null(it already contains “ab” node), hence code will go to else block.

Lets jump to line number 640. In bucket 1 we will keep iterating through the nodes till a given node’s next points to null and we will set the this next to new node(“cd” = “value-c”);
Now bucket 1 has 2 nodes .Node 1 has next as Node 2 and Node 2 has next as null

Similarly for key “ef” bucket number comes out to be 1 and it goes as next node to 2nd node of bucket 1

Now lets take map.put(“abcdef”, “value-f”);

Its hashcode is -1424385949 and bucket comes out to be (15 & -1424385949) 3

As bucket 3 is yet to be created, we create a new node there

Now lets imagine we are inserting same key again map.put(“ab”, “value-a-new”);

So at line 633 new key and old keys present will be compared using hashcode and equals method. In this case it turns out to be same

Node will remain the same. Only its value will be updated with new value

Not lets see how get() method will work – map.get(“ef”);

Again first hash would be created for the given key

We will find the bucket number using (n -1 ) & hash. It will be 1
Now this bucket has 3 nodes. It will check first node using hashcode and equals comparison. It will fail as first node had “ab” as key. After that it will iterate till next node is null and find the exact node for the given key

This is how hashmap works. This diagram sums all

 

 

Uday Ogra

Connect with me at http://facebook.com/tendulkarogra and lets have some healthy discussion :)

You may also like...

Leave a Reply

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