Understanding the Design and Thread‑Safety Mechanisms of Java ConcurrentHashMap

Preface

This article introduces common interview questions about ConcurrentHashMap and gradually reveals its design principles, aiming to help readers answer related interview topics.

While HashMap is widely used, it is not thread‑safe. To obtain thread safety, one can use ConcurrentHashMap , which provides the same functionality as HashMap but with built‑in concurrency control.

Both ConcurrentHashMap and HashMap share similar internal structures in JDK 1.8, so many design ideas are omitted to avoid repetition.

ConcurrentHashMap Principles

ConcurrentHashMap is a thread‑safe version of HashMap , using an array + linked list + red‑black tree layout internally.

Thread safety is achieved through fine‑grained locking rather than the coarse‑grained synchronized used in Hashtable . Directly applying synchronized to ConcurrentHashMap would degrade performance, so the implementation employs sophisticated designs to reduce lock contention.

Initialization follows the same power‑of‑two sizing rule as HashMap .

Improvements in JDK 1.8

In JDK 1.7, ConcurrentHashMap used an array of Segment objects with segment‑level locks ( ReentrantLock ). This required two hash calculations to locate a bucket.

JDK 1.8 removed segment locks, replacing them with CAS operations and a limited use of synchronized . The internal storage structure now mirrors that of HashMap .

Why Keys and Values Cannot Be Null

In HashMap , null keys/values are allowed, but ConcurrentHashMap forbids them to avoid ambiguity in concurrent get(key) operations. A null return could mean either "no mapping" or "mapped to null", which cannot be reliably distinguished without additional locking.

Doug Lea, the primary author, also argued that allowing nulls in concurrent collections would silently permit programming errors.

How ConcurrentHashMap Guarantees Thread Safety

The implementation relies heavily on divide‑and‑conquer techniques, using CAS for most operations and resorting to synchronized only when necessary (e.g., when a node is already present).

CAS‑Based Array Initialization

The initialization method uses a crucial variable sizeCtl with four meanings:

sizeCtl < -1 : N‑1 threads are performing resizing.

sizeCtl == -1 : Placeholder indicating array initialization is in progress.

sizeCtl == 0 : Default state, array not yet initialized.

sizeCtl > 0 : Records the next resize threshold.

CAS attempts to set sizeCtl to -1 ; if successful, the thread proceeds with initialization.

Ensuring Visibility in put Operations

The internal node array is volatile , guaranteeing visibility of the array reference but not of its elements. Access to a slot is performed via the tabAt method, which uses CAS to read the element safely.

If the node is null, casTabAt stores the new element atomically; otherwise, the node is locked with synchronized before updating.

Elegant Counting with CounterCell

Instead of a single size field, ConcurrentHashMap uses an array of CounterCell objects to reduce contention. Each cell holds a volatile long value and is updated via CAS.

private transient volatile CounterCell[] counterCells;

@sun.misc.Contended static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}

The addCount method first tries to update a base count; if contention is detected, it falls back to the counter‑cell array, initializing it lazily with fullAddCount .

Resizing Mechanism

The addCount method also checks whether the map has reached the resize threshold ( sizeCtl ). If so, a resize stamp is computed:

static final int resizeStamp(int n) {
    return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}

The stamp encodes a high‑order epoch and a low‑order thread count, ensuring that only one resize operation proceeds at a time while allowing multiple threads to assist.

During resizing, each thread works on a distinct range of buckets (divide‑and‑conquer). The migration uses synchronized on individual nodes, keeping lock granularity minimal.

Summary

The article details how ConcurrentHashMap achieves thread safety through fine‑grained locking, extensive use of CAS, a sophisticated counting scheme, and a scalable resizing algorithm. By minimizing lock contention and employing divide‑and‑conquer strategies, it provides high‑performance concurrent access compared to traditional synchronized maps.