Deep Dive into Java Concurrency: Analyzing the ConcurrentHashMap Source (Part 7)

Evolution of ConcurrentHashMap

JDK 1.5‑1.6 used a segment‑lock design: multiple Segment objects each held an independent lock, which caused high memory consumption and fixed concurrency. JDK 1.7 refined the segment lock, allowing a segment to resize without locking the whole table, but the number of segments remained a scalability limit. JDK 1.8 replaced segment locks with a combination of CAS operations and synchronized blocks, achieving finer‑grained locking, lower memory overhead, and higher concurrency.

JDK 1.7 implementation – segment lock

Core design

┌─────────────────────────────────────────────────────────────────┐
│               JDK 1.7 ConcurrentHashMap                     │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  ConcurrentHashMap                                            │
│   ┌─────────────────────────────────────────────────────┐   │
│   │  Segment[] segments (default 16)                  │   │
│   │  ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐   │
│   │  │Segment 0│ │Segment 1│ │Segment 2│ │Segment 3│   │
│   │  │ (lock) │ │ (lock) │ │ (lock) │ │ (lock) │   │
│   │  │HashEntry│ │HashEntry│ │HashEntry│ │HashEntry│   │
│   │  │ array   │ │ array   │ │ array   │ │ array   │   │
│   │  └─────────┘ └─────────┘ └─────────┘ └─────────┘   │
│   └─────────────────────────────────────────────────────┘   │
│                                                                 │
│  put operation: locate Segment → lock Segment → modify HashEntry array │
│  Different Segments can operate concurrently                │
└─────────────────────────────────────────────────────────────────┘

Code structure

public class ConcurrentHashMap<K,V> {
    // Segment array, default 16
    final Segment<K,V>[] segments;
    static final class Segment<K,V> extends ReentrantLock {
        transient volatile HashEntry<K,V>[] table;
        transient int count;
        transient int modCount;
        transient int threshold;
        final float loadFactor;
    }
    static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;
    }
}

put operation flow

public V put(K key, V value) {
    int hash = hash(key);
    int index = (hash >>> segmentShift) & segmentMask;
    Segment<K,V> s = segments[index]; // locate Segment
    return s.put(key, hash, value, false); // lock Segment internally
}

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    lock(); // ReentrantLock
    try {
        // manipulate HashEntry array, handle resize
    } finally {
        unlock();
    }
}

JDK 1.8 implementation – CAS + synchronized

Core changes

Lock mechanism : ReentrantLock (Segment) → CAS + synchronized

Data structure : Segment + HashEntry → Node array + Red‑Black tree

Lock granularity : Segment level (fixed 16) → Node level (per bucket)

Resize : Each Segment resizes independently → Whole table resizes with multi‑thread assistance

Core data structures

public class ConcurrentHashMap<K,V> {
    // Node array – core storage
    transient volatile Node<K,V>[] table;
    // Used during resize
    private transient volatile Node<K,V>[] nextTable;
    // Size control: negative values indicate resizing, -1 means uninitialized
    private transient volatile int sizeCtl;
    // Marker used during resize
    private transient volatile int transferIndex;
    // Base count for size() calculation
    private transient volatile long baseCount;
    // Counter cells for concurrent counting
    private transient volatile CounterCell[] counterCells;
    static final class Node<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
    }
    static final class TreeNode<K,V> extends Node<K,V> {
        TreeNode<K,V> parent;
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;
        boolean red;
    }
    static final class TreeBin<K,V> extends Node<K,V> {
        TreeNode<K,V> root;
        volatile TreeNode<K,V> first;
        volatile Thread waiter;
    }
}

put operation source

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;
        // 1. Initialise table if null
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        // 2. CAS insert if bucket empty
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;
        }
        // 3. Help with resize if MOVED flag seen
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        // 4. Lock bucket and insert
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) { // linked list
                        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;
                            }
                        }
                    } else if (f instanceof TreeBin) { // red‑black tree
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent) p.val = value;
                        }
                    }
                }
            }
            // 5. Treeify if binCount exceeds threshold
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null) return oldVal;
                break;
            }
        }
        addCount(1L, binCount);
        return null;
    }
}

get operation (lock‑free)

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) {
        // 1. Check first node
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // 2. If red‑black tree or resize marker
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        // 3. Traverse linked list
        while ((e = e.next) != null) {
            if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

Resizing mechanism (core difficulty)

When resize is triggered

Current table length is less than the maximum capacity.

Number of elements exceeds sizeCtl (load factor × table length).

Multi‑thread assisted resize

┌─────────────────────────────────────────────────────────────────┐
│               Multi‑Thread Assisted Resize                     │
├─────────────────────────────────────────────────────────────────┤
│ Thread A detects need to resize → creates nextTable (double size) │
│ → migrates each bucket to new table → marks migrated buckets with │
│   ForwardingNode (hash = MOVED)                                 │
│ Other threads encountering MOVED help finish the transfer       │
└─────────────────────────────────────────────────────────────────┘

ForwardingNode marker

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

JDK 7 vs JDK 8 comparison (old‑school vs modern)

Lock granularity : Segment level (fixed 16) vs Node level (per bucket).

Lock implementation : ReentrantLock vs synchronized + CAS.

Maximum concurrency : Fixed by segment count vs equal to table length.

Data structure : Linked list vs linked list + Red‑Black tree.

Resize : Independent per segment vs whole‑table multi‑thread assisted.

Performance : Medium vs High.

Memory usage : High (segment array) vs Low.

Common interview questions

Why did JDK 8 drop segment locks?

Memory consumption : Segment array and a ReentrantLock per segment increase memory usage. Fixed concurrency : The number of segments is static, limiting scalability. Lock contention : Operations within the same segment serialize. Optimization space : CAS + synchronized can shrink lock granularity to a single node, raising concurrency.

How is size() implemented?

In JDK 8, size() aggregates baseCount and the values in the CounterCell array. CounterCell distributes counting across threads to reduce contention.