How HashMap works internally in Java

In this post, we will see how HashMap works internally in java.

This post has been written with reference to Java 8. We will cover the below points in this post.

What happens when we create an object of HashMap, Map<String, String> mapObject = new HashMap<>();
What happens when we add first key-value pair.
What happens if we have a duplicate key.
What happens in case of a hash collision.

Before looking into How HashMap works internally in Java see below point.

Let’s see what happens when we create a HashMap Object and insert the first element as below.

When we create a HashMap object the default load factor of HashMap is initialized with 0.75.

Let’s see what happens when we add the first element as a key-value pair.

When we add the first key-value pair using put() method below points need to keep in mind.

  • Hash code will be calculated for the key using the hash() method.
  • The default initial capacity of HashMap will be calculated i.e 16.
  • The initial threshold will be calculated using the default initial capacity and load factor ( i.e 16 * 0.75). Don’t forget the load factor is already initialized while creating the object of HashMap using the default constructor.
  • A table will be created with initial capacity 16. Each row of the table represents a bucket.

Node<K,V>[] table = (Node<K,V>[])new Node[16];

  • Since we have a table with size 16, when we will try to add the first element it should be stored at some index. For now, suppose our first element is storing at 15th index.
  • The index will get calculated as following.

index = (n-1) & hashcode. Here n = initial capacity i.e 16. In our case since the key is ram, the hashcode of ram is 112671 using hash() method. If we do System.out.println((16-1) & 112671), the output will be 15 and yes at 15th index first pair will get stored.  We will see later how the index will be calculated details.

  • Till now, We have the table with an initial capacity 16, the default load factor is 0.75 and the initial threshold will be 12(16 * 0.75) and also index has been decided where our first element going to sit.
  • Each bucket is internally itself arrays of LinkedList and can contain more than one Nodes.


How HashMap works internally in Java

Till here we have added the first element as a key and value pair in HashMap using put() method. Before going ahead let’s see how put() method has been implemented. In put() method further putVal() method is getting called as below. Core logic has been defined inside putVal() method.

Let’s see what logic has been defined into putVal() method. Whatever we have discussed earlier once again we are going to look, how internally it’s working.

In the above code snippet line number 5 i.e resize() method is responsible to create a table and initialize it with initial capacity i.e 16. Also, the threshold value will be calculated i.e 12.

Just wait. Till now we have seen how initial capacity, the threshold is decided and also how the table is created with size 16. Did you remember in the default HashMap’s constructor we are only initializing default load factor? Table creation and some other stuff happen when put() method get called. No doubt further inside put() method putVal() is getting called and then resize() method. Hope till this point we are good. Let’s come back to putVal() method.

Now have a look at highlighted line i.e 6. What’s going on. This is the code(i = (n – 1) & hash]) which decides index, where our first element i.e (“ram”, 156) is going to stay. Let’s do one thing, just write a simple program and run separately in eclipse and observe the output.

Output is – index of our key ram is = 15

This is a brief how the index is getting calculated. Let’s have a look into this code snippet of putVal() method.

tab[i] = newNode(hash, key, value, null); Here we are calling newNode() method which is creating a new Node.

This is how our first node is creating and it will get stored into 15th index(which we can see in the above diagram). In the above code snippet, we have return new Node<>(hash, key, value, next). Here we are creating an object of  Node class. Node is an inner class which has been defined as below.

Let’s continue with How HashMap works internally in Java.

 

Let’s add another key-value (“mohan”, 168) and see what happens.

First hashcode will be calculated for key “mohan” using the hash() method.
The index will be calculated the same way(n-1 & hashcode of mohan).
The new node will get created and it will stay at some index(as of now 7th index).

How HashMap works internally in Java

 

 

Same way if we add some more element with different key and value pair, the index will be decided and a new node will be created and it will be stored at some index. Just for better understanding let’s see how does the table look after adding two key-value pairs.

Now, what will happen if we have a duplicate key? For example, suppose we are going to insert (“mohan”, 159).

 

For the above code, Since we have duplicate key hashcode will be the same and don’t forget index will also be the same as we have already seen index = (n-1) & hashcode. In this case index will 7 again. Once again have a look into putVal() method.

 

Let’s have a look at line number 5. Since we have already element at index 7, Node<K, V> p has already been initialized and if condition will not satisfied and else part will execute(new node will not be created). In else part, we have a new node Node<K, V> e which initialized with p(line 10) since if condition(line 9) is true (as we have the same key and yes equals() method will be used to compare the key). At line 15 old value will replace with the new value. This is all about what happens when we have a duplicate key.

In the above case (i.e inserting duplicate key) we have seen new node will not be created and old value will be replaced with the new value. What about the key? Do we have a new key or old one only? Key is still old mohan only value is getting changed.

 

Let’s see what is a hash collision and what happens in case of a hash collision. We are going to insert two key-value pairs, where two different keys will have the same hashcode.

Out put is – {mohan=159, 0-42L=156, 0-43-=159, ram=158}

Let’s see what going on. We have already discussed till line 12. When line 15 will execute, the index will be calculated and a new node will be created and  (“0-42L”, “156”) will stay at this index i.e 8. When line 16 will execute since we have same hashcode index will also be the same and also since we have a different key, it will create a new node which will link to the previous node which is staying at the index 8. How?

Here p = new Node(hashcode, “0-42L”, “156”, null); // Here next node will link with null someting like below.

How HashMap works internally in Java

In the above diagram at the 8th index, we have two nodes. Same way if we have some key which has hashcode 45720776 is going to stay 8th index but that must be different(it should not duplicate). This is all about what happens in case of a hash collision.

Just for better understanding –

How HashMap works internally in Java

 

How HashMap works internally in Java

 

In the two above diagram, we have two nodes in the 8th position.

Summary : –

  • HashMap uses the hash() method to calculate the hashcode of the key.
  • While creating the object of HashMap using the default constructor load factor will initialize with 0.75.
  • When we store the first key-value pair using put() method, the table will be created of type Node class(inner class) and since this is an array its size will be decided i.e 16. The initial threshold will also decide i.e 12.

Node<K,V> [] table;

  • The index will get calculated and New Node will be created and key-value will be stored to this index.
  • If the key will be duplicate, it will not create a new node, the only old value will be replaced with the new value. The equals() method will use here.
  • In case of a hash collision, the new node will be created and it will store at the same index.

That’s all about How HashMap works internally in Java.

You may like –

 

See HashMap docs here.

Summary – We have seen here how HashMap works internally in Java.

Top