How ConcurrentHashMap Guarantees Thread‑Safe Reads and Writes: A Deep Dive into C13Map Internals

1. Overview

ConcurrentHashMap (referred to as C13Map) is one of the most frequently used concurrent data structures; it backs many high‑concurrency cases and is the largest component in the JUC package (over 6000 lines). Since JDK 8 Oracle has heavily optimized it.

2. HashMap Basics

The table size is always a power of two, allowing bucket index calculation with a single bitwise AND instead of a modulo.

Hash codes are perturbed by mixing high and low 16 bits to improve randomness.

When the number of entries exceeds tableSize * 0.75, the table is resized, doubling its size each time.

Terms bucket , hash bin , and BIN all refer to the same column in the hash table.

During migration, a node’s hash determines whether its new slot is i or i + tableSize.

If a bin’s size stays below a threshold it remains a linked list; beyond the threshold it is upgraded to a red‑black tree.

HashMap itself is not thread‑safe; C13Map solves this problem.

3. C13Map Field Definitions

private static final int MAXIMUM_CAPACITY = 1 << 30; // maximum capacity
private static final int DEFAULT_CAPACITY = 16;      // default initial capacity
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // guard against OOM
private static final int DEFAULT_CONCURRENCY_LEVEL = 16; // compatibility with JDK 7
private static final float LOAD_FACTOR = 0.75f;          // resize factor
static final int TREEIFY_THRESHOLD = 8;   // list‑to‑tree threshold
static final int UNTREEIFY_THRESHOLD = 6; // tree‑to‑list threshold
static final int MIN_TREEIFY_CAPACITY = 64; // minimum size for treeify
private static final int MIN_TRANSFER_STRIDE = 16; // minimum bins moved per transfer
private static final int RESIZE_STAMP_BITS = 16; // bits for resize stamp
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; // max transfer threads
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
static final int MOVED = -1;   // forwarding node marker
static final int TREEBIN = -2; // tree bin marker
static final int RESERVED = -3; // placeholder node
static final int HASH_BITS = 0x7fffffff; // ensure positive hash after perturbation
transient volatile Node<K,V>[] table;          // current hash table
private transient volatile Node<K,V>[] nextTable; // next table during resize
private transient volatile long baseCount;      // base counter
private transient volatile int sizeCtl;          // control variable (threshold, resize stamp, etc.)
private transient volatile int transferIndex;   // lower bound for transfer
private transient volatile int cellsBusy;        // lock for CounterCell array
private transient volatile CounterCell[] counterCells; // striped counters

4. Safe Operations on Node<K,V>[]

All reads and writes to a specific index of the Node<K,V>[] array use Unsafe helpers because the array itself is volatile but its elements are not; Unsafe guarantees atomic read/write/CAS semantics on each slot.

5. Why get Is Thread‑Safe

The read path is lock‑free (except for TreeBin’s internal read‑write lock). A write acquires a synchronized lock on the bin head, ensuring at most one writer while many readers can proceed concurrently.

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if (e.hash == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        } else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

Four main cases are examined:

If table is null, the map is uninitialized – return null.

If the bin head is null, the bucket is empty – return null.

If the bin is a linked list, traverse it safely; concurrent modifications may add/remove nodes but never break the list.

If the bin is a red‑black tree, the TreeBin read‑write lock guarantees safe traversal.

ForwardingNode indicates that the bin has been moved to a new table; the read follows the find method of the forwarding node.

6. Why putValue / replaceNode Is Thread‑Safe

Node<K,V>[] tab = table;
Node f = tabAt(tab, i);
if (f == null) {
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
        break;
} else if (f.hash == MOVED) {
    helpTransfer(tab, f);
} else {
    synchronized (f) {
        if (tabAt(tab, i) == f) {
            // perform the actual put/remove/replace logic
        }
    }
}

Key safety points:

When the bin is empty, a CAS inserts the new node atomically.

If the bin is a ForwardingNode, the thread assists the transfer.

Otherwise the thread locks the bin head, double‑checks that the head has not changed, and then performs the update.

The double‑check prevents ABA‑like scenarios; because the thread holds a reference to the original head, the node cannot be reclaimed by GC before the operation finishes.

7. Atomic Compute Methods

Four methods are covered: computeIfAbsent, computeIfPresent, compute, and merge. Their differences lie in when they insert, how they handle null results, and whether they need a ReserveNode placeholder.

public V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) {
    if (key == null || remappingFunction == null)
        throw new NullPointerException();
    int h = spread(key.hashCode());
    V val = null; int delta = 0; int binCount = 0;
    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) & h)) == null) {
            Node<K,V> r = new ReservationNode<K,V>();
            synchronized (r) {
                if (casTabAt(tab, i, null, r)) {
                    binCount = 1;
                    Node<K,V> node = null;
                    try {
                        if ((val = remappingFunction.apply(key, null)) != null) {
                            delta = 1;
                            node = new Node<K,V>(h, key, val, null);
                        }
                    } finally {
                        setTabAt(tab, i, node);
                    }
                }
            }
            if (binCount != 0) break;
        } else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        // list update (omitted)
                    } else if (f instanceof TreeBin) {
                        // tree update (omitted)
                    }
                }
            }
        }
    }
    if (delta != 0) addCount((long)delta, binCount);
    return val;
}

For computeIfAbsent and compute, a ReserveNode is created when the bin is empty; this placeholder is locked while the user‑supplied function runs, preventing other threads from repeatedly performing the same expensive computation.

8. Resize Transfer Process

Three places trigger a transfer: addCount, tryPresize, and helpTransfer. The transfer works in parallel by multiple threads, each acquiring a range of bins via CAS on transferIndex. The first thread also allocates nextTable.

while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) {
    int rs = resizeStamp(n);
    if (sc < 0) {
        if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS ||
            (nt = nextTable) == null || transferIndex <= 0)
            break;
        if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
            transfer(tab, nt);
    } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) {
        transfer(tab, null);
    }
    s = sumCount();
}

The transfer algorithm:

Determine a stride (minimum 16 bins) based on CPU count.

First thread creates nextTable and sets transferIndex = n.

Each thread repeatedly CASes transferIndex to claim a segment, then moves the corresponding bins:

When all bins are processed, the last exiting thread commits nextTable to table and clears control fields.

During transfer, reads either see the old bin (still valid) or follow the ForwardingNode to the new table, guaranteeing safety.

9. Traverser (Iterator) Design

The traverser must cope with concurrent transfers. When it encounters a ForwardingNode, it pushes the current table context onto a stack, switches to the next table, and continues. When the end of a table is reached, it pops the previous context.

static final class Traverser<K,V> {
    Node<K,V>[] tab; Node<K,V> next; TableStack<K,V> stack, spare;
    int index, baseIndex, baseLimit, baseSize;
    Traverser(Node<K,V>[] tab, int size, int index, int limit) {
        this.tab = tab; this.baseSize = size; this.baseIndex = this.index = index;
        this.baseLimit = limit; this.next = null;
    }
    final Node<K,V> advance() {
        Node<K,V> e;
        if ((e = next) != null) e = e.next;
        for (;;) {
            Node<K,V>[] t; int i, n;
            if (e != null) return next = e;
            if (baseIndex >= baseLimit || (t = tab) == null || (n = t.length) <= (i = index) || i < 0)
                return next = null;
            if ((e = tabAt(t, i)) != null && e.hash < 0) {
                if (e instanceof ForwardingNode) {
                    tab = ((ForwardingNode<K,V>)e).nextTable;
                    e = null;
                    pushState(t, i, n);
                    continue;
                } else if (e instanceof TreeBin)
                    e = ((TreeBin<K,V>)e).first;
                else e = null;
            }
            if (stack != null) recoverState(n);
            else if ((index = i + baseSize) >= n) index = ++baseIndex;
        }
    }
    private void pushState(Node<K,V>[] t, int i, int n) { /* ... */ }
    private void recoverState(int n) { /* ... */ }
}

The traverser guarantees that every element present in the highest‑order table is visited at least once, even if the map is being resized concurrently.

10. Concurrent Counting (CounterCell)

To avoid the contention of a single volatile long counter, C13Map uses a striped CounterCell[] array similar to LongAdder. Each cell is updated by a thread‑local probe; if contention is detected the array expands (up to the number of CPUs).

private final void addCount(long x, int check) {
    CounterCell[] cs; long b, s;
    if ((cs = counterCells) != null || !U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell c; long v; int m;
        boolean uncontended = true;
        if (cs == null || (m = cs.length - 1) < 0 ||
            (c = cs[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended = U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) {
            fullAddCount(x, uncontended);
            return;
        }
        if (check <= 1) return;
        s = sumCount();
    }
    if (check >= 0) {
        // possibly trigger resize if count exceeds threshold (same logic as in section 8)
    }
}

The fullAddCount method handles initialization, expansion, and retry loops, mirroring the logic of LongAdder.

11. Bulk Operations (Fork/Join)

C13Map provides stream‑like bulk methods ( forEach, search, reduce, reduceValues) that are implemented by specialized BulkTask subclasses. These tasks inherit the traverser logic and run in a fork/join pool, allowing parallel processing of map entries.

static final class MapReduceMappingsTask<K,V,U> extends BulkTask<K,V,?> {
    final BiFunction<? super K,? super V,? extends U> transformer;
    final BiFunction<? super U,? super U,? extends U> reducer;
    U result;
    MapReduceMappingsTask(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
                         MapReduceMappingsTask<K,V,U> nextRight,
                         BiFunction<? super K,? super V,? extends U> transformer,
                         BiFunction<? super U,? super U,? extends U> reducer) {
        super(p, b, i, f, t);
        this.nextRight = nextRight;
        this.transformer = transformer;
        this.reducer = reducer;
    }
    public final U getRawResult() { return result; }
    public final void compute() {
        if (transformer != null && reducer != null) {
            for (int i = baseIndex, f, h; batch > 0 && (h = (f = baseLimit) + i >>> 1) > i; ) {
                addToPendingCount(1);
                (rights = new MapReduceMappingsTask<>(this, batch >>>= 1, baseLimit = h, f, tab,
                                                      rights, transformer, reducer)).fork();
            }
            U r = null;
            for (Node<K,V> p; (p = advance()) != null; ) {
                U u = transformer.apply(p.key, p.val);
                if (u != null) r = (r == null) ? u : reducer.apply(r, u);
            }
            result = r;
            for (CountedCompleter<?> c = firstComplete(); c != null; c = c.nextComplete()) {
                @SuppressWarnings("unchecked")
                MapReduceMappingsTask<K,V,U> t = (MapReduceMappingsTask<K,V,U>)c,
                    s = t.rights;
                while (s != null) {
                    U sr = s.result;
                    if (sr != null) t.result = (t.result == null) ? sr : reducer.apply(t.result, sr);
                    s = t.rights = s.nextRight;
                }
            }
        }
    }
}

12. Summary

Since JDK 8, C13Map abandoned the segment‑based design of JDK 7, moving lock granularity to individual bins and using synchronized (now heavily optimized) instead of ReentrantLock. It introduces a concurrent transfer mechanism, ForwardingNode, ReserveNode, a lightweight read‑write lock inside TreeBin, striped CounterCell counters, and Fork/Join‑based bulk tasks. The overall design relies on volatile for visibility, CAS for atomicity, and fine‑grained synchronization, making it a textbook example of a lock‑free, highly concurrent data structure.