Java Interview Questions (Series) - HashMap internals

Isn't it nice when different posts interact with each other? It's like one of those Spiderman episodes. 😅

Brief

A Map in Java refers to an object containing data in a key-value format.

❗️❓ There are a few conditions to every Map:

🔸  A map cannot contain duplicate keys.

🔸  Each key can map to at most one value.  ( We'll see what happens in case of collisions. )

🔸  The value under a key can be null.

🔸  A single null key can be added in a Map.

HashMap is one of the implementations of the Map interface along TreeMap, HashTable, ConcurrentHashMap, etc.  

Let's take a closer look into it.

Implementation

🔵  Imagine the HashMap structure as an array of buckets.

Each bucket has an index attached to it.

When first initializing a new HashMap object, it has 16 buckets.

    Map hashMap = new HashMap();

In order for a value to be assigned to a bucket, we need to calculate the index of the bucket under which the value will fall.

The method for calculating the index is a function of the key's hashcode and the number of buckets.

    index = hashCode(key) & (n-1)

Read more about hashcode and equals in this post!

🔷   Insert

Adding a pair of values in our HashMap is as simple as executing:

    Map<String, Integer> ageMap = new HashMap();

    ageMap.put("Jack", 20);

Behind the scenes, this is what happens:

1️⃣   Generate the hash code for the key "Jack".

2️⃣   Calculate the index of the bucket under which the pair should be added to.
Let's say it was 1.

3️⃣   Create the key-value pair and add it under the appropriate bucket.

Let's add a new pair.

    ageMap.put("Joe", 35);

Behind the scenes, this is what happens:

1️⃣   Generate the hash code for the key "Joe".

2️⃣   Calculate the index of the bucket, the pair to be added to.
Let's say it was 13.

3️⃣   Create the key-value pair and add it under the appropriate bucket.

❓ What happens when the generated index is of an already used bucket?

For example, let's add another pair.

    ageMap.put("John", 44);

Behind the scenes, this is what happens:

1️⃣   Generate the hash code for the key "John".

2️⃣   Calculate the index of the bucket, the pair to be added to.
Let's say it was 1.

3️⃣   Create the key-value pair and add it under the appropriate bucket.

4️⃣   Because that particular bucket is already used, they keys of the two pairs will be compared using the equals method.

5️⃣   If the keys are not the same, the new pair will be added under the same bucket following the existing pair.

❗️ Note: Buckets are implemented using LinkedLists.

6️⃣   If the keys are the same, the value will be updated to the new value.

    ageMap.put("Jack", 44);

🔷  Retrieve value

In order to retrieve a value from the HashMap, you need to provide a key.

	Integer joeAge = ageMap.get("Joe"); 

Behind the scenes, what happens is:

1️⃣   Generate the hash code for the key "Joe".

2️⃣   Calculate the index of the bucket to retrieve the value from.

3️⃣   Fetch the value under the bucket.

4️⃣   If the referred to bucket contains multiple pairs, the equals and hashcode methods are used again. It iterates through the pairs to find the exact pair and retrieve the value.