How HashMap Works Internally in Java — Explained Simply

Introduction:-

You use HashMap every day in Java. But have you ever wondered what actually happens when you write map.put("name", "Harsh")? Where does it go? How does Java find it so fast? Let's break it all down — step by step, simply.

Think of HashMap as a Building with Lockers

Imagine a building with 16 lockers (numbered 0 to 15). Each locker can hold items. When you want to store something, instead of randomly picking a locker, Java uses a smart formula to decide which locker your item goes into. That formula is called hashCode().

This building is your HashMap. Those lockers are called buckets.

What is hashCode()?

Every object in Java has a hashCode() method. It returns an integer number that represents that object.

Think of it like this — every person has a unique Aadhar number. hashCode() is Java's way of giving every object its own number.

String name = "Harsh"; System.out.println(name.hashCode()); // gives some integer like 80786770

But here's the thing — that number can be huge. You can't have 80 million lockers. So Java brings it down to fit within the current bucket size using:

bucketIndex = hashCode % numberOfBuckets

For example: hashCode = 80786770 buckets = 16 index = 80786770 % 16 = 2

So "Harsh" goes into locker number 2.

How Does Java Calculate hashCode() for a String?

This is the actual formula Java uses internally for String hashCode:

hashCode = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]*31^0

Where s[i] is the ASCII value of each character and n is the length of the string.

Example with "abc":

'a' = 97, 'b' = 98, 'c' = 99

hashCode = 97 * 31^2  +  98 * 31^1  +  99 * 31^0
         = 97 * 961   +  98 * 31    +  99 * 1
         = 93217      +  3038       +  99
         = 96354

Why 31?

• 31 is a prime number — prime numbers reduce the chance of collisions

• 31 * i = (32 * i) - i = (i << 5) - i, which is very fast for the CPU to compute

• It's large enough to spread values well but small enough to avoid overflow

What Happens When You Call put()?

map.put("Harsh", 25);

Java does these steps internally:

Step 1 — Call "Harsh".hashCode() → get a big number Step 2 — Calculate index = hashCode % 16 → find the bucket Step 3 — Store the key-value pair ("Harsh", 25) in that bucket

When you call map.get("Harsh") later:

Step 1 — Call "Harsh".hashCode() → same big number Step 2 — Calculate same index → go directly to that bucket Step 3 — Return the value

This is why HashMap is O(1) — it never searches. It directly jumps to the right locker.

Default Capacity and Load Factor

When you create a new HashMap:

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

Java creates an array of 16 buckets by default. This is the initial capacity.

Now imagine your building has 16 lockers but you keep adding more and more items. At some point the lockers get too crowded and finding things becomes slow. To prevent this, Java uses a load factor.

Load factor = 0.75 (default)

This means — when 75% of the buckets are filled, Java says "this building is getting too full, time to expand."

Threshold = capacity × loadFactor = 16 × 0.75 = 12

So when you add the 13th entry, Java automatically:

1. Creates a new array of 32 buckets (doubles the size)

2. Recalculates the bucket index for every existing entry

3. Places them all into the new bigger array

This process is called Rehashing.

Think of it like moving from a small building to a bigger one and reassigning everyone a new locker number.

What is a Collision? (The Problem)

Remember how we calculate the bucket index?

index = hashCode % 16

What if two different keys produce the same index?

"Harsh".hashCode() % 16 = 5 "Rahul".hashCode() % 16 = 5

Both "Harsh" and "Rahul" want to go into locker number 5. But a locker can only hold one thing right?

This is called a Hash Collision — two different keys landing in the same bucket.

Why Does Collision Happen?

Because we're taking a huge number (hashCode) and squeezing it into a small range (0-15). It's like trying to fit 1000 people into 16 rooms — some rooms will have multiple people.

How is Collision Resolved? (Chaining)

Java's solution is simple — each bucket doesn't hold just one item, it holds a LinkedList of items.

So when "Harsh" and "Rahul" both land in bucket 5, the bucket looks like:

Bucket 5 → ["Harsh"=25] → ["Rahul"=30] → null

Both items are stored as a chain in the same bucket.

Now when you call map.get("Rahul"):

1. Calculate index → bucket 5

2. Go to bucket 5

3. Walk through the chain — check each key using equals()

4. Find "Rahul" → return 30

This is why both hashCode() AND equals() matter in HashMap. hashCode() finds the bucket, equals() finds the exact key within the bucket.

Java 8 Improvement — From LinkedList to Tree

There's still a problem. What if 100 keys all land in the same bucket? The chain becomes very long and searching through it becomes slow — O(n).

Java 8 solved this with a smart upgrade:

▎ If a single bucket has more than 8 entries, Java converts that LinkedList into a Red-Black Tree.

Before Java 8: Bucket → [A] → [B] → [C] → ... → [100 items] O(n) After Java 8: Bucket → Red-Black Tree of those items O(log n)

A Red-Black Tree is a self-balancing tree where searching is always O(log n) — much faster than scanning a long chain.

And if entries drop below 6 (due to removal), it converts back to a LinkedList.

Full Picture — What Happens When You Do put()

map.put("Harsh", 25);

1. "Harsh".hashCode() is called → returns some integer

2. index = hashCode % capacity → finds bucket number

3. If bucket is empty → store directly

4. If bucket is not empty (collision): - Walk through the chain - Use equals() to check if key already exists - If yes → update the value - If no → add to the end of the chain

5. After insertion, check if size > threshold (capacity × 0.75) - If yes → rehash (double the capacity, recalculate all indexes)

Summary Table

One Line to Remember

▎ HashMap uses hashCode() to find the bucket fast, equals() to find the exact key within the bucket, chaining to handle collisions, and rehashing to stay efficient as it grows.