HashMap Internal Working

Understanding how HashMap works internally is a top-tier interview topic. This covers hashing, buckets, collisions, equals/hashCode, resizing, and Java 8 optimizations.

High-Level Idea

A HashMap stores data as key–value pairs using hashing to achieve fast access.

Key → hashCode() → index (bucket) → Entry (key, value)
          

Core Internal Structure

Java 8+ Internal Data Structure

• Array of buckets
• Each bucket contains:
  • Linked List (few collisions)
  • Red-Black Tree (many collisions)

Bucket[ ]  →  Node / TreeNode
          

Step-by-Step: put(key, value) Flow

1️⃣ hashCode() Calculation

HashMap calls:

int hash = key.hashCode();
          

2️⃣ Index (Bucket) Calculation

HashMap computes index using bitwise AND:

index = (n - 1) & hash;
          

Where:

• n = current capacity (default 16)

• ✔ Faster than modulo (%)
• ✔ Works because capacity is always a power of 2

3️⃣ Insert into Bucket

• If bucket is empty → insert entry
• If bucket is not empty:
  • Compare keys using equals()
  • If key exists → replace value
  • Else → add new node (collision)

Collision Handling (Critical)

Java 7 and Earlier

• Linked List only
• Worst-case time: O(n)

Java 8 and Later (Major Improvement)

• Linked List → Red-Black Tree when:
  • Bucket size ≥ 8
  • Table capacity ≥ 64
• ✔ Improves worst-case performance to O(log n)

equals() and hashCode() Role

Both are used:

1. hashCode() → bucket location
2. equals() → key equality within bucket

Same hashCode ≠ same key

equals() decides final match

What Happens with Duplicate Keys?

map.put(1, "Java");
map.put(1, "Python");
          

• ✔ Key found using equals()
• ✔ Old value replaced
• ✔ No exception

Default Capacity & Load Factor

When Does Rehashing Occur?

Rehashing happens when:

size > capacity × loadFactor
          

Example:

16 × 0.75 = 12
          

✔ On inserting 13th entry → resize

Rehashing Process

1. Capacity doubles (16 → 32)
2. All entries are rehashed
3. Buckets are redistributed

⚠ Costly operation

✔ Amortized performance still O(1)

Why Capacity Is Power of 2 (Interview Favorite)

• Enables fast index calculation
• Uniform distribution of keys
• Efficient resizing logic

(n - 1) & hash   // instead of hash % n
          

Treeification Conditions (Java 8+)

A bucket converts to Red-Black Tree only if:

✔ Prevents premature tree creation

null Key Handling

HashMap allows one null key.

map.put(null, "Java");
          

Internally:

• null key always maps to bucket 0

Time Complexity (Interview Table)

(Java 8+)

Common Interview Traps

• Forgetting treeification conditions
• Saying HashMap is always O(1)
• Ignoring equals() role
• Using mutable objects as keys
• Forgetting rehashing cost

Best Practices (Real-World)

• Override both equals() and hashCode()
• Use immutable keys
• Set initial capacity when size is known
• Avoid excessive collisions
• Use ConcurrentHashMap for concurrency

Interview-Ready Answers

Short Answer

HashMap stores key–value pairs using hashing and buckets.

Detailed Answer

Internally, HashMap uses an array of buckets where each bucket stores entries using linked lists or red-black trees. The key’s hashCode determines the bucket index, and equals is used to resolve collisions. Java 8 optimizes collision handling by converting long chains into balanced trees, ensuring efficient performance.

Key Takeaway

HashMap = Hashing + Buckets + equals/hashCode + Smart Resizing. Mastering internals is essential for performance tuning, correctness, and interview success.