Unlocking Java 8 ConcurrentHashMap: A Deep Dive into Lock‑Free Scaling and Performance

Overview

The article analyses the internal implementation of Java 8 ConcurrentHashMap, comparing it with the Java 7 version and showing how the newer design achieves higher concurrency by reducing lock granularity and using lock‑free techniques.

ForwardingNode

During resizing, a special node type ForwardingNode marks a bucket that has been transferred to the new table and forwards get operations to the new bucket array, avoiding blocking during expansion.

static final class ForwardingNode<K,V> extends Node<K,V> {
    final Node<K,V>[] nextTable;
    ForwardingNode(Node<K,V>[] tab) {
        super(MOVED, null, null, null);
        this.nextTable = tab;
    }
}

CAS Operations

The JDK 8 implementation relies heavily on UNSAFE.compareAndSwapInt and compareAndSwapLong for atomic updates, such as the compareAndSwapInt method for int fields and the compareAndSwapLong method for long fields.

public final native boolean compareAndSwapInt(Object o, long offset, int expected, int x);
public final native boolean compareAndSwapLong(Object o, long offset, long expected, long x);

If the object’s field at the given offset equals the expected value, it is atomically set to the new value and true is returned; otherwise false is returned.

Initialization

The table is lazily initialized. The first thread that detects a null table performs a CAS on sizeCtl to set it to -1, then creates the bucket array and sets sizeCtl to the resize threshold (approximately 0.75 of the capacity).

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0) {
            Thread.yield();
        } else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[]) new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

Put Method

The public put method delegates to putVal. If the target bucket is empty, a CAS inserts a new node without locking. If the bucket contains nodes, the method synchronizes on the first node, checks for hash collisions, updates existing entries, or appends a new node. During resizing, a ForwardingNode may cause the thread to help with transfer.

public V put(K key, V value) {
    return putVal(key, value, false);
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    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) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;
        } else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent) e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value, null);
                                break;
                            }
                        }
                    }
                }
            }
            break;
        }
    }
    addCount(1L, binCount);
    return null;
}

Dynamic Resizing

When the map reaches its resize threshold, multiple threads cooperate to transfer entries to a new table twice as large. The shared variable transferIndex acts as a cursor; each thread atomically claims a range of buckets using CAS on transferIndex. A ForwardingNode marks transferred buckets.

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE;
    if (nextTab == null) {
        try {
            @SuppressWarnings("unchecked")
            Node<K,V>[] nt = (Node<K,V>[]) new Node<?,?>[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        transferIndex = n;
    }
    // ... core transfer loop omitted for brevity ...
}

Size Counting

To avoid contention on a single counter, ConcurrentHashMap maintains a base count ( baseCount) and an array of CounterCell objects. Updates first try to CAS the base count; on contention they fall back to per‑thread cells, which are combined in sumCount() for the size() operation.

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

private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        // update cell or retry
        fullAddCount(x, true);
    }
    // resize check omitted
}

final int size() {
    long n = sumCount();
    return (n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n;
}

final long sumCount() {
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}

Key Takeaways

Java 8 removes the segment array and uses per‑bucket ForwardingNode for lock‑free resizing.

CAS operations replace most explicit locks, reducing contention.

Size counting is distributed across CounterCell instances to avoid a single hotspot.

The design closely mirrors HashMap’s resizing logic while adding concurrency optimizations.