1 of 22

Video Series | Java Interview Questions

Internal Working of

Hashmap

2 of 22

Internal memory structure of Hashmap.

How put() method internally works.

What exactly is Hash Collision

Use of equals() and hashCode() in HashMap

Java 8 enhancement to HashMap

3 of 22

Internal structure or working of Hashmap.

HashMap<String, String> map = new HashMap<>();

What internally happens when,

JVM creates new HashMap

So, let’s begin…..

To understand the internal working of HashMap, we should know what happens when JVM executes this line code here.

Here on this line we are creating a new HashMap.

So,... when we ask JVM to create a new HashMap, then what JVM does is….in the heap memory, …….

Okay, Why heap memory ?? right, because in Java objects are created inside heap memory and HashMap is an object in Java.

So, in heap memory….JVM will create 16 buckets as you can see here in the diagram.

Okay, so these are not literally the buckets, but the analogy with water bucket is same.

In our water buckets, we store water, soo similarly this is a data bucket where we store data.

So let’s represent buckets in computer programming notion, okay, yeah, this looks better

Now you know, JVM has created 16 buckets in the heap memory for storing items into them.

And how JVM stores elements in there, that part we will some time

4 of 22

Internal structure or working of Hashmap.

only 16 buckets..??

So what if I want to put more than 16 items..??

Load Factor

CONCEPT

If HashMap reaches more than 75% of it’s capacity then it doubles the existing capacity

75%

5 of 22

Internal structure or working of Hashmap.

Before diving into the internals, let’s see what exactly inside a bucket.!!

Linked List

Start

item-1

P

Let’s see what happens when we ADD nodes to Linked List

item-2

P

item-3

P

Before diving into the internals, let’s see what exactly is a bucket and how data is stored in the bucket.

So, here bucket is nothing but the Linked List. Linked List is one the important data structures.

You might already know about the LinkedList and how the elements are added to Linked List.

But let’s quickly revise this once because we will need this ahead.

Linked list stores data in the form of a NODEs. Each Node consists of mainly 2 things - obviously the DATA that we want to store and a pointer which points to next node.

Let’s see how the nodes are added to the linked list.

Initially we have zero nodes that is nothing in the linked list.

Then we added first node with item-1….. So what is Item- is nothing but our data, it can be anything like an Object or Primitive type

Now we have only one node in our linked list

And the pointer in this node points to null because there is no other node.

Now when we add next node to the linked list, then the pointer of 1st node will point to next node.

Now when we add one more node in Linked List. then the pointer of 2nd node points to this new node.

And this way - one by one the Nodes can be added to the linked list.

Now I guess you know that a bucket is nothing but the linked list and you know what is Linked list and what are the Nodes.

6 of 22

Internal structure or working of Hashmap.

Now we know

How exactly buckets of HashMap look like

16

map.put( “key” , “value” );

7 of 22

Internal structure or working of Hashmap.

Let’s see what happens when we put() items to HashMap

map.put( “FB” , ”A” );

“FB” => String Object

KEY

VALUE

Step-1: find hashcode

“FB”.hashCode()

Step-2: find bucket index

hashcode & (length-1)

= 2236 & (16 - 1)

hashcode = 2236

bucket index = 12

Example-1

hashcode of FB = 2236 | index 12

As we already know Hashmap is used to store key value pair.

Let’s try to put key-value pair in the hashmap.

Here “FB” is a key and “A” is a value.

So, when we try to put key-value pair, what JVM will do is get the KEY from key value pair.

The key must be an object, primitive values are not acceptable.

Then JVM will get the HashCode() of KEY. here in this case hashcode is 2236.

If you don’t know, the HashCode() method is coming from Object class. As In Java Object class is the parent of all other classes.

And now you know JVM needs to get the hashcode of key, and only objects can have hashcode… that’s why we can’t use primitives in hashmap..okay???

Now we have hascode of key…. From this hashcode JVM will calculate the bucket index using this formula here. So in this case the bucket index is calculated as 12.

That means this key-value pair will go into 12th index bucket as a node of Linked list..

8 of 22

Internal structure or working of Hashmap.

map.put( “FB” , ”A” );

bucket index = 12

0.

1.

2.

12.

15.

..

[ “FB” , “A” ]

P

1st node Linked List

Example-1

hashcode of FB = 2236 | index 12

9 of 22

Internal structure or working of Hashmap.

Let’s put one more item to the HashMap

map.put( “LD” , ”B” );

“LD” => String Object

Step-1: find hashcode

“LD”.hashCode()

Step-2: find bucket index

hashcode & (length-1)

2424 & (16 - 1)

hashcode = 2424

bucket index = 8

Example-2

hashcode of FB = 2236 | index 12

10 of 22

Internal structure or working of Hashmap.

map.put( “LD” , ”B” );

bucket index = 8

0.

8.

..

[ “LD” , “B” ]

P

1st nodes in

different buckets

12.

[ “FB” , “A” ]

P

..

Example-2

hashcode of FB = 2236 | index 12
hashcode of LD = 2424 | index 8

11 of 22

Internal structure or working of Hashmap.

Let’s put one more item to the HashMap

hash-collision

map.put( “Ea” , ”C” );

“Ea” => String Object

Step-1: find hashcode

“Ea”.hashCode()

Step-2: find bucket index

hashcode & (length-1)

2236 & (16 - 1)

hashcode = 2236

bucket index = 12

Example-2

hashcode of FB = 2236 | index 12
hashcode of LD = 2424 | index 8
hashcode of Ea = 2236 | index 12

12 of 22

Internal structure or working of Hashmap.

map.put( “Ea” , ”C” );

bucket index = 12

0.

8.

..

[ “Ea” , “B” ]

[ “LD” , “B” ]

P

1st nodes in

different buckets

12.

[ “FB” , “A” ]

P

..

Example-3

hashcode of FB = 2236 | index 12
hashcode of LD = 2424 | index 8
hashcode of Ea = 2236 | index 12

Hash Collision

13 of 22

Internal structure or working of Hashmap.

map.put( “Ea” , ”C” );

bucket index = 12

0.

8.

..

[ “Ea” , “B” ]

12

[ “FB” , “A” ]

P

Example-3

hashcode of FB = 2236 | index 12
hashcode of LD = 2424 | index 8
hashcode of Ea = 2236 | index 12

Check if two objects are equal?

“Ea”.equals(“FB”)

[ “Ea” , “C” ]

P

14 of 22

Internal structure or working of Hashmap.

Summary

map.put( “key” , “value” )

Find hashCode() of the key:

“key”.hashCode()

Find bucket index using hashcode:

Hashcode & ( length - 1 )

Hash Collision

Simply add to Linked List as first node

No

Yes

Key already present??

“key”.equals(“existing-key”)

No

Yes

Add to Linked List by replacing existing equal node

Add to

Linked List as next node

15 of 22

Internal structure or working of Hashmap.

How put() method internally works.

What exactly is Hash Collision

Use of equals() and hashCode() in HashMap

Java 8 enhancement to HashMap

16 of 22

Java 8 enhancement to HashMap

Searching in Linked List

Start

item-1

P

item-2

P

item-3

P

item-4

P

How to find node with item-3 ?

Item-3 == item-1

Item-3 == item-2

Item-3 == item-3

item-3

Return node with item 3

Before we see how to get key-value pair from HashMap… let’s see how searching works in Linked list.

Suppose we want to search Node with item-3..

While searching through the Linked list, we cannot directly jump to 3rd node...we have to traverse the list one by one from the beginning.

And that is the only drawback of linked list because it reduces performance, as I have to go to the given node by traversing the node before it.

So, while searching for node with item-3, we will first go to first node and check if it contains item3 or not.

No, it doesn’t contain item-3… the go to next node..we can go to next node from first node because it has the pointer which points to next node.

So again on this next node, check if item-3 is present…. No it isn't here as well.

Then go to 3rd node...check if it has item-3…. Yessss.. It has item-3 .. now return this node…

So, this is how searching works in linked list

17 of 22

Java 8 enhancement to HashMap

get() method of HashMap

map.get ( “Ea” );

0.

1.

12.

15.

..

[ “FB” , “A” ]

P

8.

[ “Ea” , “C” ]

P

Step 1: HashCode of Ea | 2236

Step 2: Find bucket index | 12

Go to bucket index 12

Get the [key-value] pair

..

[ “Ea” , “C” ]

Now you know how to search in Linked list…

Let’s see how to get key-value pair from Hashmap..

So, here get() method of hashmap is use to get the value from hashmap that we have already added.

This is the speciality of HashMap.. get() method of hashmap returns the value very fast.. In general get() method of hashmap has the complexity of O(1)

Suppose we want to find the key-value pair with key as “Ea”

Then first,,, JVM will find the hashcode of key that is “Ea”

Hashcode is 2236

Then calculate the bucket index as we have seen in previous examples..

Now JVM knows that the required key-value pair present in 12th bucket index.

So, JVM will go to 12th bucket and get the required node and returns the node.

But you can see that bucket with index 12 already has 2 nodes….

So, to find node with “Ea” JVM will have to go and search one by one through nodes until JVM reaches the required node…

Although the get() method can find bucket index very quickly but searching through the linked list can create performance problem if it has too many nodes..

In general hashMap doesn’t have multiple nodes in single bucket because hash collision is rare scenarios..so it would be having only one node and that;s he searching would be faster..

But this is in general scenario..

So, now we know that.. If the bucket has more number of nodes, then finding item in that bucket will take more time.

That means performance will degrade.

18 of 22

Java 8 enhancement to HashMap

HashMap<String, String> map = new HashMap<>( );

map.put ( “AaAaAa” , “v1” );

map.put ( “AaAaBB” , “v2” );

map.put ( “AaBBAa” , “v3” );

map.put ( “AaBBBB” , “v4” );

map.put ( “BBAaAa” , “v5” );

map.put ( “BBAaBB” , “v6” );

map.put ( “BBBBAa” , “v7” );

map.put ( “AaBBBB” , “v8” );

map.put ( “BBBBBB” , “v9” );

=> 1952508096

19 of 22

Java 8 enhancement to HashMap

0.

1.

2.

12.

15.

..

AaAaAa

P

AaAaBB

P

AaBBAa

P

AaBBBB

P

BBAaAa

P

BBAaBB

P

..

Performance Degradation

20 of 22

Java 8 enhancement to HashMap

0.

12.

15.

..

4

P

2

P

7

P

6

P

5

P

..

3

P

1

P

Uses compareTo() method.

compareTo() method is use to check the order of items

It’s a red-black tree.

binary search tree

Self balancing

TREEIFY_THRESHOLD

So, when number of nodes in the given bucket reaches TREEFY_THRESHOLD then this LINKED LIST will be converted to TREE…

Let’s see how the elements are stored in Tree…

Suppose we want to store integer values in tree.

Consider first node is with integer value 4.

Then comes node with value 6… it will go above here..because 6 is greater than 4

Then comes 2, it will go down.. Because 2 is smaller than 4

Then comes 7… it is greater than 4 as well as 6 then it will go above 6..

Then comes 3.. It is smaller than 4 so it will go down..but greater than 2 so will be above 2..

Then comes 5 and will be added to tree

Then comes 1 and will be added to tree

So, this is how the elements are added to the Trees…

Now what is the benefit…over linked list????

Now suppose you want to search for node with integer 1..

Then JVM will first got to start node that node with value 4..

Now JVM knows 1 is smaller than 4.. So it will go down to node with 2…

Now JVM knows 1 is smaller than 2 then it will further go down and then will reach the required node.

So, instead of traversing through all nodes.. JVM has to traverse very few nodes to reach actual node..

So this will improve the performance…

So, there are few more things that you should know.

First one is… JVM uses compareTo() method to decide whether the value is smaller or greater or equal while adding into tree..

Second thing is..

This tree is also called as a red-black tree.

It is a binary search tree and a self balancing tree..

And that’s it…. Now you are ready for all questions related to Hashmap...

21 of 22

NEXT VIDEO

22 of 22

References and attributions:

Icons made by <a href="https://www.flaticon.com/authors/freepik" title="Freepik">Freepik</a> from <a href="https://www.flaticon.com/" title="Flaticon"> www.flaticon.com</a>

Icons made by <a href="https://www.flaticon.com/authors/wanicon" title="wanicon">wanicon</a> from <a href="https://www.flaticon.com/" title="Flaticon"> www.flaticon.com</a>

Icons made by <a href="https://www.flaticon.com/authors/freepik" title="Freepik">Freepik</a> from <a href="https://www.flaticon.com/" title="Flaticon"> www.flaticon.com</a>

Icons made by <a href="https://www.flaticon.com/authors/iconixar" title="iconixar">iconixar</a> from <a href="https://www.flaticon.com/" title="Flaticon"> www.flaticon.com</a>