When HashMap starts killing production: the engineering story of ConcurrentHashMap

Imagine a typical production service.

• 32 CPU
• hundreds of threads
• configuration / session / rate limits cache
• tens of thousands of operations per second

And somewhere inside — a regular Map.

At first, everything looks harmless.

Map<String, Session> sessions = new HashMap<>();

Then a couple of threads appear.

Then dozens.

Then production load begins.

And suddenly:

• latency spikes
• CPU goes to 100%
• strange freezes appear
• sometimes — infinite loops in HashMap

This is not a hypothesis. These are real production incidents that occurred in large Java systems before the advent of proper concurrent structures.

It is from such stories that ConcurrentHashMap was born.

But to understand why it is designed this way, one must go through the entire evolution:

HashMap
   ↓
synchronized Map
   ↓
Segmented ConcurrentHashMap (JDK7)
   ↓
CAS + bin locking (JDK8)
   ↓
tree bins + lock striping + resize migration

And this is one of the most beautiful engineering evolutions in the JVM.

Tree bins are a mechanism in HashMap and ConcurrentHashMap (starting from Java 8), whereby a bucket with a large number of collisions is automatically transformed from a linked list to a balanced red-black tree. This prevents performance degradation when there are many elements with the same hash: instead of linear complexity O(n) for search, insertion, and deletion operations, they are performed in O(log n). Such a transformation occurs when the number of elements in a bucket exceeds a specified threshold (usually 8), and serves as protection against both bad hashCode and potential hash collision attacks.

---

First naive idea: just synchronized

The most obvious protection for HashMap:

Map<K, V> map = Collections.synchronizedMap(new HashMap<>());

Or:

public synchronized V get(K key)
public synchronized V put(K key, V value)

This works.

But only until real concurrency appears.

What happens under load

32 threads
200k ops/sec

Each call:

lock(map)
   → read/write
unlock(map)

We get a global lock.

Diagram

Thread1 ─┐
Thread2 ─┤
Thread3 ─┤
Thread4 ─┤ → LOCK(map) → operation → unlock
Thread5 ─┤
Thread6 ─┘

All threads line up in a queue.

Even get() blocks all other get().

This is a fundamental problem.

---

Second attempt: lock striping

The Java engineers decided:

"What if we divide the map into several independent parts?"

Thus, ConcurrentHashMap JDK7 was born.

Segments

ConcurrentHashMap
 ├─ Segment 0
 ├─ Segment 1
 ├─ Segment 2
 └─ Segment 3

Each segment is a separate mini HashMap with its own lock.

segment = hash(key) % segments

Now:

Thread1 → Segment1 → lock
Thread2 → Segment2 → lock
Thread3 → Segment3 → lock

And they do not interfere with each other.

Operation code

Segment<K,V> s = segments[(hash >>> segmentShift) & segmentMask];
s.lock();

try {
    s.put(key, value);
} finally {
    s.unlock();
}

Performance improvement

But new problems arose.

---

Problem #1 — Fixed Parallelism

The number of segments is fixed.

16 segments

But the server:

64 threads

As a result again:

Thread1 → Segment3
Thread2 → Segment3
Thread3 → Segment3

Contention returns.

---

Problem №2 — resize

Resize — the most difficult part of any hash map.

capacity = capacity * 2

In the segmented model:

resize → lock entire segment

This is expensive.

---

Problem #3 — memory overhead

Each Segment contains:

ReentrantLock
table
metadata

On large maps, this turns into memory waste.

The JVM engineers decided:

We need a structure without segments.

Thus, ConcurrentHashMap JDK8 was born.

---

Architecture of ConcurrentHashMap (JDK8)

Node<K,V>[] table

Each bucket is managed separately.

table
 ├─ bin0
 ├─ bin1
 ├─ bin2
 ├─ bin3

Main idea

---

End-to-End put operation

map.put("user42", session);

Step 1 — hash

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

This protects against bad hashCode.

Step 2 — index

index = (n - 1) & hash

Bit mask is faster than modulo.

Step 3 — CAS insertion

if (casTabAt(tab, i, null,
      new Node<>(hash, key, value)))
      break;

CAS = Compare And Swap.

if (table[i] == null)
    table[i] = node

But atomically at CPU level.

CAS is performed through Unsafe.compareAndSwapObject and maps to the CPU instruction cmpxchg.

Why this is important

CAS avoids lock.

Thread1 → CAS success
Thread2 → CAS fail → retry

No kernel switch.

---

When CAS Does Not Help

If the bucket is not empty:

bin0 → node → node → node

Local lock is used:

synchronized (f) {
    // modify chain
}

Lock is only for one bucket.

---

When a bucket turns into a tree

If:

bucket size > 8

List turns into a Red-Black Tree.

O(log n)

Diagram

before

bucket
  ↓
  N → N → N → N → N


after

        N
      /   \
     N     N
    / \   / \

---

Resize — the most difficult part

ConcurrentHashMap performs resize without global pause.

Cooperative migration

old table
 ├─ bin0
 ├─ bin1
 ├─ bin2
 └─ bin3

Thread1 → bin0
Thread2 → bin1
Thread3 → bin2
Thread4 → bin3

Threads help move buckets.

ForwardingNode

ForwardingNode

This is a signal:

"this bucket has already moved"

---

Java Memory Model

volatile Node<K,V>[] table;

This ensures visibility between threads.

put → happens-before → get

---

CPU Cache Effects

CAS invokes:

invalidate cache line

If many threads hit one bucket:

cache ping-pong

Performance drops.

---

Impact on GC

Node
 key
 value
 next

Millions of Node → load on GC scanning.

---

Real production case

Map<IP, Counter>

load:

150k req/sec

Replacement:

synchronized HashMap
↓
ConcurrentHashMap

---

Main trade-offs

---

The most important engineering idea

ConcurrentHashMap is a combination of three strategies:

optimistic (CAS)
pessimistic (locks)
structural (tree bins)

Each is used only when needed.

---

Engineering Intuition

If:

high concurrency
frequent reads
rare writes

ConcurrentHashMap is ideal.

But if:

writes dominate

CAS can turn into a retry storm.

---