ConcurrentHashMap is a thread-safe, high-performance HashMap from the J.U.C package, widely used in concurrent programming scenarios.

API Usage

ConcurrentHashMap extends the Map interface, so its API is similar to HashMap. This analysis focuses on the put and get methods as entry points to understand the internal mechanisms.

Source Code Analysis (JDK 1.8)

Version Comparison: JDK 1.7 vs JDK 1.8

Both ConcurrentHashMap and HashMap share a similar underlying principle, but ConcurrentHashMap is more complex due to its concurrency requirements.

• JDK 1.7: ConcurrentHashMap is composed of Segment arrays. Each Segment inherits from ReentrantLock and locks a portion of the map. By locking individual segments, thread safety is ensured. With default settings, up to 16 threads can write concurrently if they operate on different segments.

Two Key Improvements in JDK 1.8

1. Removed Segment Design: Instead of using segments, JDK 1.8 uses a Node array to store data and locks individual array elements (each bucket) to reduce contention further.

2. Data Structure Change: The underlying structure evolved from an array of linked lists to an array of linked lists plus red-black trees. In cases where hash collisions cause long linked lists (length > 8), the list is converted to a red-black tree. This reduces worst-case lookup time from O(n) to O(log n), improving performance.

The structure is similar to that of JDK 1.8's HashMap, but ConcurrentHashMap incorporates more complexity to ensure thread safety.

Analyzing put and get Methods

put Method

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

The internal putVal method:

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;
        }
        // ...
    }
    // ...
}

When two threads operate concurrently, if thread A successfully executes casTabAt, thread B will immediately see the updated table[i] via tabAt. This is because casTabAt has volatile read/write semantics; according to the volatile happens-before rule, thread A's write is visible to thread B's subsequent read.

initTable Method

Initializes the Node array with a suitable size.

• sizeCtl: This control flag indicates the state of initialization or resizing.
  • Negative values: -1 means initialization is in progress; -N means (N-1) threads are performing resizing.
  • 0: Node array not yet initialized.
  • Positive: The threshold for the next resize (e.g., 0.75 * 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;
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

tabAt Method

This method retrieves the element at a given index using Unsafe.getObjectVolatile. Although the table array is declared volatile, volatile semantics apply only to the array reference, not its elements. To ensure visibility of updates to individual elements, Unsafe is used to perform volatile reads.

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);
}

Second Phase of put: addCount

After inserting a new node, addCount increments the element count and may trigger a resize.

addCount(1L, binCount);
return null;

addCount Details

• x: number of elements to add (usually 1).
• check: if >= 0, a resize check is performed.

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)) {
        CounterCell a; long v; int m;
        boolean uncontended = true;
        if (as == null || (m = as.length - 1) < 0 ||
            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended =
              U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            fullAddCount(x, uncontended);
            return;
        }
        if (check <= 1)
            return;
        s = sumCount();
    }
    // resize check logic
}

Why CounterCell?

Using a single variable to track size under high contention would be inefficient due to CAS failures and spin loops. Instead, ConcurrentHashMap uses a CounterCell array to distribute the count across multiple cells, reducing contention. The sumCount method aggregates these values:

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

fullAddCount Analysis

This method initializes CounterCell or retries adding to it, handling concurrency.

Key points:

• It uses ThreadLocalRandom.getProbe() to get a random probe for the current thread (avoids performance issues with Random).
• The cellsBusy flag is used as a CAS lock when initializing or expanding the CounterCell array.
• If the array is full (size >= CPU cores) or contention is high, it tries to CAS on baseCount as a fallback.

Resizing: transfer Method

When the element count exceeds the threshold, the table is resized. The resizeStamp method generates a unique stamp for each resize:

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

This stamp is used to coordinate multiple threads during resizing. The sizeCtl is set to (rs << RESIZE_STAMP_SHIFT) + 2 for the first thread, and subsequent threads increment it by 1 when joining.

Data Migration During Resize

The migration logic splits a linked list into two parts based on hash & n. This determines whether the node stays in the same bucket index (low part) or moves to the index + old capacity (high part).

synchronized (f) {
    if (tabAt(tab, i) == f) {
        Node<K,V> ln, hn;
        if (fh >= 0) {
            int runBit = fh & n;
            Node<K,V> lastRun = f;
            for (Node<K,V> p = f.next; p != null; p = p.next) {
                int b = p.hash & n;
                if (b != runBit) {
                    runBit = b;
                    lastRun = p;
                }
            }
            if (runBit == 0) {
                ln = lastRun;
                hn = null;
            } else {
                hn = lastRun;
                ln = null;
            }
            for (Node<K,V> p = f; p != lastRun; p = p.next) {
                int ph = p.hash; K pk = p.key; V pv = p.val;
                if ((ph & n) == 0)
                    ln = new Node<K,V>(ph, pk, pv, ln);
                else
                    hn = new Node<K,V>(ph, pk, pv, hn);
            }
            setTabAt(nextTab, i, ln);
            setTabAt(nextTab, i + n, hn);
            setTabAt(tab, i, fwd);
            advance = true;
        }
        // Red-black tree handling omitted for brevity
    }
}

Why High/Low Partition?

The partitioning avoids recalculating hash values after resize. When the array length doubles from n to 2n, elements with hash & n == 0 stay in the same index, while those with hash & n != 0 move to index + n. This is because the bit used for indexing is the next higher-order bit, and the new index is determined directly by that bit.

helpTransfer Method

If a thread encounters a ForwardingNode (hash value MOVED), it means another thread is already resizing. The current thread can help by calling helpTransfer:

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; int sc;
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
        int rs = resizeStamp(tab.length);
        while (nextTab == nextTable && table == tab &&
               (sc = sizeCtl) < 0) {
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}

put Method: Adding to Existing Bucket

If the bucket is not empty, the thread locks the head node (synchronized (f)), then traverses the linked list or tree:

• If the key already exists, optionally overwrite the value.
• Otherwise, append a new node at the end of the list (or insert into the tree).

put Method: After Insertion

After insertion, if binCount reaches TREEIFY_THRESHOLD (8), the treeifyBin method is called:

if (binCount >= TREEIFY_THRESHOLD)
    treeifyBin(tab, i);

treeifyBin first checks if the table length is less than MIN_TREEIFY_CAPACITY (64). If so, it prefers resizing (tryPresize) over converting to a tree. Otherwise, it converts the linked list to a red-black tree.

tryPresize Method

This method is used both for resizing and initializing. It attempts to resize the table to atleast the given size, coordinating with other threads if a resize is already in progress.