📦 Section 4 · Question #19

How does ConcurrentHashMap ensure thread-safety

The ConcurrentHashMap class delivers thread safety in multi-threaded architectures without resorting to coarse global object locking. Instead of forcing all threads to queue beh...

📦 Collections 📄 Source Markdown

🟢 Junior Level

1. Fundamental Principle of Thread Safety

The ConcurrentHashMap class delivers thread safety in multi-threaded architectures without resorting to coarse global object locking. Instead of forcing all threads to queue behind a single monitor (as in legacy Hashtable or Collections.synchronizedMap), ConcurrentHashMap coordinates three cooperative low-level mechanisms:

  1. Lock-Free Reads (get): Read operations execute without acquiring any locks whatsoever, running concurrently with active write operations.
  2. Atomic CAS (Compare-And-Swap): CPU-level atomic instructions insert new elements into unoccupied buckets with zero lock contention.
  3. Fine-Grained Node-Level Synchronization: When a hash collision occurs, ConcurrentHashMap synchronizes strictly on the head node of that specific bucket (synchronized (head)). All other buckets in the hash table remain completely open for simultaneous parallel writes by other threads.
Thread 1 ──► put("A", 1) ──► Bucket [2] (Locks monitor of node 'A')
Thread 2 ──► put("B", 2) ──► Bucket [7] (Unoccupied, CAS insertion, runs concurrently!)
Thread 3 ──► get("C")    ──► Bucket [5] (Lock-free volatile read, runs concurrently!)

🟡 Middle Level

1. Java Memory Model (JMM) Guarantees & Volatile Visibility

Inside ConcurrentHashMap, bucket array elements and node fields are explicitly declared with volatile semantics:

// Internal table bucket array:
transient volatile Node<K,V>[] table;

// Collision chain node definition:
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;          // Volatile value reference!
    volatile Node<K,V> next; // Volatile successor link!
}

Why Read Operations (get) are Completely Lock-Free:

  1. Bucket array elements are accessed via tabAt(table, i) using volatile load semantics (via Unsafe / VarHandle).
  2. The payload reference val and the collision pointer next are both declared volatile.
  3. Under the Java Memory Model specification, writing to a volatile variable establishes a formal Happens-Before relationship with any subsequent read of that same variable.
  4. A reading thread is guaranteed to observe the most recent value written by any thread without acquiring a mutual exclusion lock (mutex).

2. Step-by-Step Insertion Lifecycle: putVal()

When a thread calls map.put(key, value):

                          ┌───────────────────────────┐
                          │   Invoke put(key, value)  │
                          └─────────────┬─────────────┘
                                        │
                         Hash Spread: spread(key.hashCode())
                                        │
                                        ▼
                                ┌───────────────┐
                     ┌──────────┤ table == null?├──────────┐
                     │          └───────────────┘          │
                  YES│                                     │ NO
                     ▼                                     ▼
           initTable() via CAS                  Index i = (n - 1) & hash
                     │                                     │
                     └──────────────────┐                  ▼
                                        │         ┌─────────────────┐
                                        └────────►│  table[i] empty?│
                                                  └────────┬────────┘
                                                 YES│             │ NO
                                                    │             │
                    ┌───────────────────────────────┘             ▼
                    ▼                                   ┌────────────────────┐
        CAS: casTabAt(table, i, null, node)             │ hash == MOVED (-1)?│
                    │                                   └─────────┬──────────┘
           ┌────────┴────────┐                                 YES│         │ NO
        SUCCESS            FAIL                                   │         │
           │                 │                                    │         ▼
         DONE              RETRY              helpTransfer() ◄────┘   synchronized (head) {
                                                                        Insert into List/Tree
                                                                      }
  1. Null Validation: If key == null or value == null, it immediately throws NullPointerException.
  2. Hash Code Spreading: hash = (h ^ (h >>> 16)) & HASH_BITS, preserving non-negative integers for standard nodes.
  3. Empty Bucket Insertion (CAS): If table[i] == null, the thread attempts an atomic casTabAt(table, i, null, node):
    • If the slot is still null, the node is inserted in 1 CPU clock cycle without locking.
    • If a peer thread beat it to the slot, CAS returns false, and the loop retries.
  4. Resizing Co-operation (MOVED): If head.hash == -1 (MOVED), the bucket is currently migrating; the thread calls helpTransfer() to accelerate the resize.
  5. Collision Resolution (synchronized): If elements already exist in the bucket, the thread acquires the intrinsic monitor of the head node: 
    synchronized (f) {
    if (tabAt(tab, i) == f) { // Double-Check: verifies head has not changed
        if (fh >= 0) {
            // Linear traversal: update existing key or append to tail
        } else if (f instanceof TreeBin) {
            // Red-Black Tree insertion
        }
    }
}
  6. Treeification: If collision chain length reaches 8 (TREEIFY_THRESHOLD) and capacity $\ge 64$, treeifyBin() converts the bucket into a Red-Black Tree (TreeBin).

🔴 Senior Level

1. Cooperative Distributed Resizing (ForwardingNode & helpTransfer())

Unlike HashMap where resizing locks or destabilizes the entire structure, resizing in ConcurrentHashMap is concurrent, distributed, and cooperative:

  1. When capacity thresholds are crossed, the initiating thread allocates nextTable with double the size ($2N$).
  2. The table is partitioned into chunks of buckets called strides (minimum 16 buckets per thread).
  3. As soon as a thread finishes migrating a bucket to nextTable, it places a sentinel ForwardingNode with hash -1 (MOVED) into the old bucket, pointing to nextTable.
  4. Cooperation: Any thread arriving to execute put(), remove(), or merge() that encounters a ForwardingNode does not block; it invokes helpTransfer(), claims an unclaimed stride of buckets, and helps transfer entries in parallel.
  5. Non-blocking Reads during Resizing: A thread invoking get() on a bucket holding a ForwardingNode does not wait; it calls ForwardingNode.find(), searching the already-migrated node directly in nextTable.

2. Special Sentinel Nodes Encoded via Negative Hashes

ConcurrentHashMap encodes internal node archetypes using negative hash codes on the bucket head:

Node Type Hash Code Architectural Role
Node<K,V> $\ge 0$ Standard single-linked collision list entry
ForwardingNode -1 (MOVED) Resizing placeholder; routes get() to nextTable
TreeBin -2 (TREEBIN) Red-Black Tree root wrapper; manages tree read/write lock bits
ReservationNode -3 (RESERVED) Placeholder for atomic computeIfAbsent() execution

The Role of ReservationNode:

When computeIfAbsent(key, mappingFunction) is invoked for a key mapping to an empty bucket, the map cannot know the result of mappingFunction beforehand. To prevent race conditions, the thread installs a ReservationNode via CAS, acquires synchronized (reservationNode), computes the value via the user lambda, and atomically replaces the sentinel with the newly computed Node.

3. Architectural Evolution: Why Java 8 Abandoned Segments

In Java 7, ConcurrentHashMap was composed of an array of Segment<K,V> instances (each extending ReentrantLock):

  • Problem 1: Fixed concurrency level (default 16 segments). Maximum simultaneous writers was strictly capped at 16, regardless of CPU core counts or table capacity.
  • Problem 2: High memory footprint from allocating 16 heavy ReentrantLock objects and their associated AbstractQueuedSynchronizer (AQS) queues.
  • Problem 3: size() had to lock all segments sequentially if concurrent modifications occurred during two non-blocking probe passes.

In Java 8+, the architecture transitioned to Node-Level Locking:

  • Locks are placed directly on the existing Node object header using intrinsic synchronized(head).
  • Eliminates auxiliary lock objects, slashing heap footprint.
  • Concurrency scales dynamically with table capacity (thousands of concurrent write channels).
  • Leverages HotSpot’s intrinsic monitor optimizations (biased locking, adaptive spinning, lock coarsening).

4 Tricky Questions

1. Why does reading get() require no locks even while another thread is restructuring the collision list or treeifying?

Answer:

  1. Volatile Link Visibility: Node.val and Node.next are volatile. In a singly-linked list, modifications append to the tail or update values in place; readers traversing next references observe consistent, fully initialized state via JMM Happens-Before guarantees.
  2. Atomic TreeBin Read-Write State: When a bucket converts to a Red-Black Tree (TreeBin), writers acquire an internal state lock. However, readers do not block on this lock: if a writer is holding the tree lock, TreeBin.find() falls back to traversing an auxiliary singly-linked list that is maintained alongside the tree.
  3. Resizing Delegation: If a bucket is being transferred, the reader encounters a ForwardingNode and transparently searches nextTable via ForwardingNode.find().

2. Why does putVal() perform a double-check if (tabAt(tab, i) == f) inside synchronized (f)?

Answer: This is an application of the Double-Checked Locking pattern. Between the moment the thread observed node f at index i via tabAt() and the moment it successfully acquired the intrinsic lock synchronized (f), a context switch could occur. During that window, another thread could have deleted the node, converted the bucket to a TreeBin, or replaced the bucket with a ForwardingNode during a resize. The check confirms that f remains the genuine, current head of bucket i.

3. Why did the Java 8 architects choose intrinsic synchronized (node) over ReentrantLock for bucket head locking?

Answer:

  1. Memory Footprint: Each ReentrantLock is an independent heap object with an inner Sync subclass extending AQS, consuming 32–48 bytes of heap memory. Allocating a ReentrantLock for every bucket in a table with 65,536 buckets would squander megabytes of memory. In contrast, synchronized(node) requires zero additional objects, utilizing the existing 8-byte Mark Word inside the node’s object header.
  2. JVM Compiler & Hardware Optimization: HotSpot applies adaptive spinning, lock coarsening, and lock elision directly to intrinsic monitors. Under low contention, entering an uncontended synchronized block executes via a single CAS on the Mark Word with zero OS kernel context switches.

4. What is the role of ReservationNode (hash -3) during computeIfAbsent(), and what concurrency problem does it solve?

Answer: When computeIfAbsent() is called on an empty bucket slot, the value must be generated by executing a user-provided lambda. If the map simply executed the lambda and then attempted a CAS, two concurrent threads could execute the expensive lambda simultaneously, causing duplicate computation. To prevent this, ConcurrentHashMap installs a ReservationNode (with hash RESERVED = -3) into the empty slot using CAS before running the lambda. It synchronizes on this node, executes the user’s mapping function safely, and then replaces the ReservationNode with the actual computed node.

🎯 Interview Cheat Sheet

30-Second Elevator Pitch

“ConcurrentHashMap in Java 8+ achieves high-throughput thread safety using a three-tier architecture:

  1. Lock-Free Reads: get() uses zero locks, reading volatile array slots (tabAt), volatile val, and volatile next references under JMM Happens-Before rules.
  2. Lock-Free Empty Bucket Writes: Empty slots are populated via atomic CPU Compare-And-Swap (casTabAt).
  3. Fine-Grained Node-Level Locking: Bucket collisions lock strictly the first node of that bucket (synchronized(head)), allowing thousands of parallel writes to different buckets. Resizing is cooperative and parallelized via ForwardingNode and helpTransfer(), while sizing is scaled across threads via CounterCell stripes.”

High-Impact Architectural Facts

  • Memory Optimization: Uses synchronized(headNode) rather than ReentrantLock to avoid allocating lock objects; uses the node’s native Mark Word header.
  • Negative Sentinel Hashes: MOVED (-1) indicates resizing; TREEBIN (-2) indicates Red-Black Tree; RESERVED (-3) reserves a slot for computeIfAbsent().
  • Double-Checked Locking: Validates tabAt(tab, i) == head inside synchronized(head) to guard against concurrent structural mutations.
  • TreeBin Readers Never Block: If a thread is writing to a TreeBin, reading threads traverse a secondary linked list maintained alongside the tree.

Common Pitfalls & Red Flags

  • ❌ Believing Java 8 CHM uses Segments: Segments were eliminated in Java 8; modern CHM locks individual bucket head nodes.
  • ❌ Assuming get() acquires read locks: get() is 100% lock-free in all scenarios.
  • ❌ Wrapping ConcurrentHashMap in external synchronization: Destroys parallel execution; use compute(), merge(), or putIfAbsent().
  • ❌ Running slow or blocking code in computeIfAbsent(): Holds the bucket monitor lock, blocking all peer operations on that bucket.