How does ConcurrentHashMap ensure thread-safety?

🟢 Junior Level

ConcurrentHashMap is thread-safe thanks to three mechanisms:

CAS — for inserting into an empty bucket (no locks)
Volatile — so all threads see the latest data
Synchronized — only for collisions (locks a single bucket)

How they work together:

CAS = inserting a new element without locks
Volatile = visibility of changes between threads (each thread immediately sees new elements)
Synchronized = protection on collisions (when two threads write to the same bucket simultaneously)

// Safe from different threads:
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// Thread 1:
map.put("A", 1);

// Thread 2 (simultaneously):
map.put("B", 2);

// Both are safe!

🟡 Middle Level

Three pillars of safety

1. CAS (Compare-And-Swap):

// For an empty bucket:
if (CAS(table[i], null, newNode)) {
    // Success! Inserted without locks
} else {
    // Another thread inserted → retry
}

2. Volatile:

// All fields are volatile:
transient volatile Node[] table;
volatile V val;
volatile Node next;

// → Writes by one thread are visible to all
// → get() without locks!

3. Synchronized per bucket:

// On collision:
synchronized (firstNode) {  // Only this bucket!
    // Insert/remove
}
// → Other buckets work in parallel!

Atomic methods

map.putIfAbsent(key, value);      // Atomic
map.computeIfAbsent(key, func);   // Atomic
map.merge(key, value, func);      // Atomic

// Without these methods:
// ❌ Race condition!
// Race condition step by step:
// Thread 1: containsKey = false (key not present)
// Thread 2: containsKey = false (key still not present)
// Thread 1: put(key, value1)  ← inserted
// Thread 2: put(key, value2)  ← OVERWRITES! Lost update.
if (!map.containsKey(key)) {
    map.put(key, value);  // Another thread can slip in!
}

🔴 Senior Level

When NOT to use ConcurrentHashMap

Single-threaded access — overhead of CAS/volatile for no reason
Read-only map after publication — HashMap is enough (after safe publication)
Need null values — CHM prohibits null keys and values

ForwardingNode and parallel Resizing

// On resize:
// Old bucket → ForwardingNode

// Writer thread sees ForwardingNode:
if (node instanceof ForwardingNode) {
    // Helps with resizing!
    table = helpTransfer(table, forwardingNode);
}

→ Resize is distributed, doesn't block all threads!

CounterCells (LongAdder pattern)

LongAdder — strategy: instead of a single volatile variable (contention on concurrent writes), an array of counters. Each thread writes to its own cell, result = sum of all cells.

// Instead of a single volatile size:
transient volatile CounterCell[] counterCells;

// Each thread:
counterCells[hash(threadId) & mask].value++;

// size() = sum(counterCells)

→ Minimal contention!

Treeification protection

> 8 elements in a bucket → red-black tree
→ Even under Hash DoS attack: O(log n)

// Node → TreeNode replacement
// Synchronization still on HEAD

ReservationNode

ReservationNode = a placeholder node that locks the bucket while the value is being computed in computeIfAbsent. Prevents duplicates from other threads.

// computeIfAbsent for an empty bucket:
// Inserts ReservationNode → synchronizes on it
// → Prevents duplicates while the function computes

Contention diagnostics

// If CHM is slow:
// 1. async-profiler → blocked state
// 2. Many threads on CHM.put
// 3. → All hitting one bucket!

// Cause: bad hashCode()
// → All keys hash to one bucket
// → Synchronized on a single bucket
// → 0 parallelism!

// Solution: rewrite hashCode()

Java 7 vs Java 8+

Java 7: Segment[] segments (16 fixed)
  → Lock per segment
  → size() = locks ALL segments

Java 8+: Node-level locking
  → Lock per bucket
  → CAS for empty buckets
  → size() = sum of CounterCells
  → Parallel resizing

Best Practices

CAS = lock-free for new keys
Volatile = visibility without locks
Synchronized = only per bucket
helpTransfer = parallel resize
CounterCells = scalable size()
Bad hashCode = the main enemy
compute = don’t block for long

Summary for Senior

CAS for empty buckets, Synchronized for collisions
Volatile = lock-free reads
ForwardingNode = parallel resize
CounterCells = LongAdder pattern for size
Treeification = DoS protection
Bad hashCode = contention = 0 parallelism
helpTransfer = threads help with resizing

🎯 Interview Cheat Sheet

Must know:

Three thread-safety mechanisms: CAS (lock-free insertion into empty bucket), volatile (visibility between threads), synchronized (collision protection at bucket level)
CAS = atomic CPU instruction: “write the new value only if the current equals the expected.” Two threads write simultaneously — one succeeds, the other retries.
Volatile fields: table, Node.val, Node.next — get() without locks, happens-before guarantee
Synchronized only on the bucket HEAD — other buckets work in parallel
Atomic methods: putIfAbsent, computeIfAbsent, merge — replace check-then-act (race condition)
ForwardingNode on resize — writer threads see it and call helpTransfer() (parallel resize)
CounterCells = LongAdder pattern: array of counters, each thread writes to its own cell, size() = sum
Treeification at > 8 elements per bucket — Hash DoS protection, O(log n) even under attack
ReservationNode in computeIfAbsent — placeholder prevents duplicates from other threads

Frequent follow-up questions:

Why can’t you replace CHM with HashMap in multi-threaded code? — Race condition: two threads simultaneously do containsKey = false, both do put — one overwrites the other. Lost updates.
What is a race condition in the context of Map? — Thread 1 checked “key not present”, Thread 2 checked “key not present”, both inserted — the second overwrites the first. Solved by computeIfAbsent (atomic).
How to diagnose contention in CHM? — async-profiler shows blocked time. Cause: bad hashCode() → all keys in one bucket → synchronized on a single bucket → 0 parallelism.
How does Java 8+ CHM differ from Java 7? — Java 7: Segment[] (16 fixed, lock per segment). Java 8+: node-level locking + CAS, parallel resize, CounterCells.

Red flags (DO NOT say):

❌ “CHM locks the entire map on write” — only one bucket (synchronized on HEAD)
❌ “get() in CHM uses synchronized” — no, lock-free reads through volatile
❌ “CHM uses Segment locking in Java 8+” — that’s outdated, now it’s node-level locking
❌ “computeIfAbsent can be replaced with containsKey + put” — no, that’s not atomic, race condition

Related topics:

[[18. What is ConcurrentHashMap]]
[[12. How does HashSet work internally]]
[[14. What is Map and what implementations exist]]
[[20. What is CopyOnWriteArrayList]]