Unlocking ConcurrentHashMap: How Java Achieves Thread‑Safe Scaling and Fast Lookups

Preface

To understand ConcurrentHashMap you need knowledge of the Java Memory Model, CAS, and HashMap internals.

Why study ConcurrentHashMap?

More flexible use than HashTable.

Learn Doug Lea’s concurrency techniques beyond simple locking.

Key Questions

How does get retrieve key/value safely?

How does put insert safely?

How is size calculated safely?

How does resizing improve concurrency?

Related Concept: Amdahl’s Law

Amdahl’s law shows that the maximum speed‑up of a program is limited by the portion that must execute serially; reducing lock contention is essential for scalability.

Thread‑Safe Initialization

HashMap stores entries in a Node[] array. In JDK 8 the array is lazily created on the first put. Initialization uses a volatile sizeCtl flag and a CAS operation so that only one thread performs the allocation while others spin.

static final class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    ...
}

Each thread checks sizeCtl. If it is negative, another thread is initializing; the thread yields and retries. The successful thread creates the Node[] and publishes it via a volatile write.

Put Operation Thread‑Safety

The putVal method computes the hash, locates the bucket, and attempts a lock‑free insertion with CAS. If the bucket is empty, a CAS stores a new node. If a node already exists, the method synchronizes on the first node of the bucket, walks the chain, and either updates an existing entry or appends a new node. When the chain length exceeds eight, the bucket is transformed into a red‑black tree.

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f;
        int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                new Node<>(hash, key, value, null)))
                break;
        } else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            // lock‑based insertion ...
        }
    }
    // update count, possibly resize
}

Resize Operation Thread‑Safety

When the map’s size exceeds a threshold, the bucket array is doubled. Multiple threads can participate in the transfer. Each thread claims a range of indices using CAS on transferIndex. Nodes are split into low‑order and high‑order lists (ln and hn) based on the new capacity bit, and each list is placed into the new array without additional locking. A special ForwardingNode marks migrated slots so that concurrent gets and puts can continue to operate on the new table.

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    // calculate stride based on CPU count
    // claim a range with CAS on transferIndex
    // for each bucket:
    //   if null, CAS to ForwardingNode
    //   else split list into low and high parts
    //   place low part at index i, high part at i + n
    //   replace old bucket with ForwardingNode
}

Thread‑Safe Size Counting

ConcurrentHashMap maintains a baseCount and an array of CounterCell objects. When contention is low, a CAS increments baseCount. Under contention, threads are mapped to cells using a thread‑local probe; each cell is updated with a CAS. If cells become full, the array is doubled. The total size is obtained by summing baseCount and all cell values.

static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}

Get Operation Thread‑Safety

Gets use the volatile tabAt method to read the bucket reference, guaranteeing visibility of the latest node. If a bucket contains a ForwardingNode (during resize), the get follows the forwarding pointer to the new table.

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab,
        ((long)i << ASHIFT) + ABASE);
}

JDK 7 vs JDK 8

JDK 7 used segmented locks—each segment was a small HashMap protected by a ReentrantLock. JDK 8 replaced segments with fine‑grained lock‑striping at the bucket level, reducing contention and improving scalability.

Conclusion

ConcurrentHashMap combines CAS, volatile fields, lock striping, and cooperative resizing to achieve high concurrency with thread‑safe operations. Understanding these techniques provides insight into designing scalable concurrent data structures.