# 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