Skip to content

# Part 4.2 — HashMap Internal Implementation Deep Dive

This is the level of understanding expected for senior Java and JVM-focused interviews.

Typical questions include:

  • Explain what happens inside HashMap.put().
  • Why does HashMap use powers of two?
  • How does resizing work?
  • What changed in Java 8?
  • Why is resize expensive?
  • What was the Java 7 infinite loop bug?

1. Internal Fields

Simplified HashMap source:

public class HashMap<K,V> {

    transient Node<K,V>[] table;

    transient int size;

    int threshold;

    final float loadFactor;

    transient int modCount;
}

Let's understand each field.

table

Node<K,V>[] table;

This is the bucket array.

Example:

Index

0
1
2
3
4
5
6
7

↓

Node

↓

Node

↓

Node

Initially:

table = null;

The bucket array is not allocated until the first insertion (lazy initialization).

size

int size;

Number of key-value pairs.

Example:

map.put(1,"A");
map.put(2,"B");

size = 2

threshold

Resize limit.

Formula:

threshold = capacity × loadFactor

Example:

Capacity = 16

Load Factor = 0.75

Threshold = 12

The 13th insertion triggers a resize.

loadFactor

Default:

0.75f

One of the best trade-offs between memory usage and collision frequency.

modCount

Tracks structural modifications.

Used for fail-fast iterators.

Example:

map.put(1,"A");

modCount++

We'll revisit this when covering iterators.

2. Lazy Initialization

Interview question:

Does new HashMap<>() allocate 16 buckets immediately?

Answer:

No.

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

Internally:

table = null

Only after:

map.put(1,"A");

does HashMap allocate:

capacity = 16

Why?

To avoid allocating memory for maps that remain empty.

3. The put() Algorithm

Suppose:

map.put("Apple",100);

Simplified flow:

put()

↓

hash()

↓

bucket index

↓

bucket empty?

↓

YES

↓

insert

↓

DONE

If not empty:

bucket

↓

compare keys

↓

existing?

↓

replace value

↓

else

↓

append/tree insert

4. hash() Method

Java 8 implementation:

static final int hash(Object key) {

    int h;

    return (key == null)
            ? 0
            : (h = key.hashCode()) ^ (h >>> 16);
}

Interview question:

Why doesn't HashMap simply use hashCode()?

Because some classes produce poor hash distributions.

Java mixes the high and low bits to improve bucket distribution.

Example:

Original

110101010101001011110000

↓

Shift

000000000000000011010101

↓

XOR

Better distribution

5. Bucket Index

Interview favorite.

Formula:

index = (capacity - 1) & hash;

Suppose:

Capacity = 16

capacity - 1 = 15

1111

Hash:

101011001

AND operation:

101011001

000001111

------------

000001001

=

9

Bucket:

9

Why Not %?

Instead of:

hash % capacity

Java uses:

hash & (capacity - 1)

Reasons:

  • Faster bitwise operation.
  • Works correctly because capacity is always a power of two.

6. Bucket Empty

Example:

Bucket 5

↓

empty

Insert node.

Bucket 5

↓

Apple

O(1)

7. Existing Bucket

Suppose:

Bucket

↓

Apple

↓

Orange

Insert:

Banana

HashMap:

  • Traverses nodes
  • Compares hashes
  • Compares keys using equals()

If found:

Replace value.

Otherwise:

Append node (or tree insert if treeified).

8. Resize Trigger

Default:

Capacity = 16

Threshold = 12

Insert 13th entry.

size = 13

↓

resize()

9. Resize Algorithm

Old table:

16 buckets

New table:

32 buckets

HashMap does not simply copy the old array.

Every node must be redistributed.

Old Bucket

↓

Node

↓

New Bucket

Each entry is relocated based on the new capacity.

10. Java 8 Resize Optimization

This is a commonly asked interview topic.

Suppose:

Old capacity:

16

New capacity:

32

For each entry, Java 8 checks one bit:

(hash & oldCapacity)

Only two possibilities exist:

Case 1

Bit = 0

Entry stays at the same index.

Old Bucket 5

↓

New Bucket 5

Case 2

Bit = 1

Entry moves.

Old Bucket 5

↓

New Bucket

5 + 16

=

21

No full hash recomputation is required.

This significantly improves resize performance.

11. Why Resize is Expensive

Suppose:

1 million entries

Resize:

Allocate larger array

↓

Visit every node

↓

Redistribute

↓

Update references

Complexity:

O(n)

Although put() is O(1) on average, the occasional resize incurs linear cost. This is why insertion is described as amortized O(1).

12. Choosing Initial Capacity

Interview scenario:

Expected entries:

1000

Bad:

new HashMap<>();

Several resizes will occur.

Better:

new HashMap<>(2048);

Why 2048?

We need:

1000 / 0.75

≈1334

Next power of two:

2048

This avoids costly resizes during population.

13. Java 7 Infinite Loop Bug

One of the classic interview questions.

Problem:

HashMap was never thread-safe.

Two threads resizing simultaneously could corrupt bucket links.

Result:

Node

↓

Node

↓

Node

↑

|
Loop

Traversal:

map.get(...)

could become:

A

↓

B

↓

C

↓

B

↓

C

↓

B

↓

Forever

CPU:

100%

Application hangs.

Why?

During resize, Java 7 reversed linked-list order while transferring nodes. Under concurrent modification, pointer updates could produce cycles.

Java 8 redesigned the transfer algorithm, reducing this specific failure mode—but HashMap is still not thread-safe.

14. HashMap Is Not Thread-Safe

Example:

Thread 1

map.put(1,"A");

Thread 2

map.put(2,"B");

Without synchronization:

  • Lost updates
  • Inconsistent internal state
  • Visibility issues

Use:

ConcurrentHashMap

for concurrent access.

15. Memory Layout

HashMap

↓

table[]

↓

Bucket

↓

Node

↓

key

value

next

Node structure:

class Node<K,V>{

    int hash;

    K key;

    V value;

    Node<K,V> next;
}

If a bucket is treeified, nodes become TreeNode instances with additional fields like parent, left, right, prev, and a color bit for the red-black tree.

16. Time Complexity

Operation Average Worst
put O(1) O(log n)
get O(1) O(log n)
remove O(1) O(log n)
resize O(n) O(n)

17. Senior Interview Questions

Q1. Why is capacity always a power of two?

To allow efficient bucket index calculation using:

(hash & (capacity - 1))

and to distribute keys evenly.

Q2. Why does Java mix hash bits?

To reduce collisions caused by poor hashCode() implementations.

Q3. Why is resize expensive?

Every entry must be visited and redistributed into the new bucket array.

Q4. Why is insertion called amortized O(1)?

Most insertions are constant time. Only occasional resizes require O(n) work, so the average cost per insertion remains constant.

Q5. Can two different keys have the same bucket?

Yes.

This is a collision.

HashMap resolves collisions using linked lists or red-black trees.

Because entries are not globally sorted. HashMap is optimized for hashing-based lookup, not ordered search.

Common Mistakes

❌ "HashMap internally stores data in a linked list."

Correct:

It stores data in an array of buckets. Each bucket may contain:

  • Nothing
  • A linked list
  • A red-black tree

❌ "HashMap lookup is always O(1)."

Correct:

Average:

O(1)

Worst case:

O(log n)

(or O(n) for non-treeified buckets or pathological cases).

❌ "HashMap is synchronized."

Correct:

It is not thread-safe.

Key Takeaways

  • HashMap is fundamentally an array-backed hash table.
  • Bucket index is computed with (capacity - 1) & hash.
  • Hash spreading improves key distribution.
  • Resizing doubles the capacity and redistributes entries.
  • Java 8 optimizes resize by checking a single bit (hash & oldCapacity).
  • Resizing is O(n), making insertion amortized O(1).
  • HashMap is not safe for concurrent modifications; use ConcurrentHashMap when needed.
  • Understanding these internals is a hallmark of a strong senior Java candidate.

Next: Part 4.3 — 50+ HashMap Interview Questions and Scenario-Based Discussions

We'll cover:

  • Tricky interviewer questions
  • Real production debugging scenarios
  • putIfAbsent() vs computeIfAbsent()
  • Why mutable keys break maps
  • Memory leaks with maps
  • Hash collision edge cases
  • Coding and troubleshooting questions commonly asked in senior interviews.