Java HashMap Internals Explained in Simple Terms

Java HashMap Internals Explained in Simple Terms (With Examples & Time Complexity)

Java HashMap is one of the most frequently asked topics in Java interviews.
Many developers use it daily, but very few understand how it actually works internally.

In this article, we will explain:

• What HashMap is

• How HashMap stores data internally

• Role of hashCode() and equals()

• What collisions are and how they are handled

• Improvements made in newer Java versions

• Time complexity of all major operations

• How to reduce frequent collisions

All explanations are in simple terms, with examples.

---

1. What Is a HashMap?

A HashMap stores data in key–value pairs.

Example:

Map<String, Integer> map = new HashMap<>();
map.put("A", 10);
map.put("B", 20);

Key characteristics:

• Keys must be unique

• Values can be duplicated

• Order is not guaranteed

• One null key is allowed

• Multiple null values are allowed

Why HashMap is popular:

HashMap provides very fast access to data.

---

2. How HashMap Stores Data Internally

Internally, HashMap uses:

• An array (called bucket array)

• Each position in the array is called a bucket

Each bucket stores Node objects.

A Node contains:

• key

• value

• hash

• next reference

So internally, HashMap is:

Array + LinkedList + Tree (from Java 8 onwards)

---

3. What Happens When You Call put()

When you write:

map.put(key, value);

HashMap performs the following steps:

Step 1: Call hashCode()

HashMap calls:

key.hashCode()

This returns an integer number.

Example:

"A".hashCode() → 65

---

Step 2: Improve Hash Distribution

Java internally modifies the hash to spread bits better:

hash = h ^ (h >>> 16)

This reduces collisions.

---

Step 3: Calculate Bucket Index

index = (n - 1) & hash

Where:

• n is the capacity of HashMap

• Capacity is always a power of 2 (16, 32, 64…)

This gives a valid bucket index.

---

Step 4: Insert the Node

• If bucket is empty → store node

• If bucket already has data → collision handling starts

---

4. Why Capacity Is Always Power of 2

HashMap always keeps its capacity as a power of 2.

Reason:

• Enables fast index calculation using bitwise AND

• Avoids expensive modulo operation

• Distributes keys evenly

If you pass:

new HashMap<>(20);

Internally, capacity becomes:

32

---

5. Role of hashCode() and equals()

This is extremely important for interviews.

Rule to remember:

hashCode() decides the bucket
equals() decides the key match

During put():

1. HashMap finds the bucket using hashCode()

2. It checks existing keys using equals()

3. If equals() returns true → value is replaced

4. Otherwise → new entry is added

If these methods are implemented incorrectly:

• Duplicate keys may appear

• Data may not be retrievable

---

6. What Is a Hash Collision?

A collision happens when:

• Two different keys

• Produce the same bucket index

Example:

Key A → bucket 3
Key B → bucket 3

Collisions are normal and expected.

HashMap is designed to handle them.

---

7. Collision Handling Before Java 8

Before Java 8:

• Each bucket used a LinkedList

Structure:

Bucket 3 → Node1 → Node2 → Node3

Search required traversing the list.

Time Complexity (Before Java 8):

• Best case → O(1)

• Worst case → O(n)

If many keys land in one bucket, performance becomes poor.

---

8. Collision Handling From Java 8 (Major Improvement)

Java 8 introduced Red-Black Trees.

Treeification rules:

LinkedList converts to Tree when:

• Bucket size > 8

• Total capacity ≥ 64

After conversion:

• LinkedList → Red-Black Tree

• Faster search

Time Complexity (Java 8+):

• Worst case → O(log n)

This change greatly improved HashMap performance.

---

9. How get() Works Internally

When you call:

map.get(key);

Steps:

1. Calculate hash

2. Find bucket index

3. If bucket empty → return null

4. Traverse LinkedList or Tree

5. Use equals() to match key

6. Return value

---

10. How remove() Works Internally

Remove operation:

map.remove(key);

Steps:

• Locate bucket

• Find node using equals()

• Remove node

• Update pointers or tree structure

---

11. Resize and Rehashing

Default values:

• Initial capacity = 16

• Load factor = 0.75

Resize happens when:

size > capacity × load factor

During resize:

• Capacity doubles

• All keys are rehashed

• Buckets are recalculated

Resize is expensive but happens infrequently.

---

12. Time Complexity of HashMap Operations

Operation	Average Case	Worst Case (Java 7)	Worst Case (Java 8+)
put()	O(1)	O(n)	O(log n)
get()	O(1)	O(n)	O(log n)
remove()	O(1)	O(n)	O(log n)
resize()	–	O(n)	O(n)

Interview takeaway:

HashMap provides O(1) average performance with improved worst-case behavior in Java 8.

---

13. How to Reduce Frequent Collisions

Best practices:

1. Use immutable keys

2. Implement hashCode() properly

3. Override equals() correctly

4. Avoid constant hashCode values

5. Increase initial capacity if size is known

6. Prefer Java 8 or newer

---

14. Why HashMap Is Not Thread-Safe

HashMap does not use synchronization.

Problems in multi-threading:

• Data inconsistency

• Lost updates

• Infinite loops (older versions)

For multi-threading:

• Use ConcurrentHashMap

---

Final Summary

• HashMap uses hashing and buckets

• hashCode() chooses the bucket

• equals() confirms the key

• Collisions handled using LinkedList and Tree

• Java 8 improved worst-case performance

• Time complexity is critical for interviews

If you understand this article fully, HashMap interview questions become easy.