Java ConcurrentHashMap Internals: Lock-Free CAS & Fine-Grained Bucket Sync

Suppose you are building an API rate-limiting gateway handling 100,000 HTTP requests per second across 32 CPU worker threads.

Your gateway tracks IP request counts inside a shared map:

Map<String, Integer> requestCounts = ...;

If you use a standard HashMap, concurrent writes corrupt internal bucket node references, trapping threads in infinite loops or dropping counter updates.

If you wrap the map in Collections.synchronizedMap(new HashMap<>()) or use Hashtable, every thread must acquire a single global monitor lock before reading or writing. 31 CPU cores sit idle waiting for 1 core to release the global lock. Throughput collapses.

Java’s ConcurrentHashMap solves high-concurrency contention by abandoning global locks entirely.

---

Evolution: JDK 7 Segmented Locking vs JDK 8+ CAS

JDK 7: Segmented Locking (16 Array Locks)

In JDK 7, ConcurrentHashMap divided its internal bucket table into 16 independent Segment regions (sub-hashtables).

ConcurrentHashMap (JDK 7)
  |
  +---> Segment[0] (ReentrantLock) ---> Buckets [0..15]
  +---> Segment[1] (ReentrantLock) ---> Buckets [16..31]
  +---> Segment[2] (ReentrantLock) ---> Buckets [32..47]

Threads writing to different segments executed concurrently. However, concurrent writes within the same segment still blocked each other.

---

JDK 8+: Lock-Free CAS + Fine-Grained Bucket Locks

JDK 8 eliminated Segment objects completely. It uses a flat node table (Node<K,V>[] table) and applies two lock-free concurrency techniques:

1. CAS (Compare-And-Swap) for inserting nodes into empty bucket slots.
2. Synchronized Bucket Head Locking when inserting into an existing collision chain.

Node Table Array
[ 0 ] ---> null  (Inserting here uses lock-free CAS!)
[ 1 ] ---> synchronized(HeadNode) { Node1 -> Node2 } (Only locks bucket 1!)
[ 2 ] ---> null

If Thread A writes to bucket 1 and Thread B writes to bucket 5, both threads execute simultaneously without blocking.

---

Lock-Free CAS Insertion into Empty Buckets

When a thread inserts a key whose calculated bucket index is currently null, the JVM attempts an atomic hardware-level Compare-And-Swap operation via VarHandle or Unsafe:

// Simplified JDK 8+ ConcurrentHashMap putVal logic
final V putVal(K key, V value) {
    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) {
            // Lock-free CAS insertion into empty bucket!
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break; // Atomic insertion succeeded without acquiring a lock!
        }
        else {
            // Bucket slot occupied! Lock ONLY the first node of this bucket.
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // Traverse collision list or Red-Black tree node...
                }
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

---

Volatile Reads: Zero Lock Retrieval

get() operations in ConcurrentHashMap acquire zero locks.

Node values and next pointers are declared volatile:

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

When a write thread updates a volatile field, the CPU flushes the write buffer directly to main RAM. Read threads see updated node values instantly across CPU caches without acquiring synchronized locks.

---

Concurrent Sizing: CounterCell Striped Addition

In a multi-threaded system, updating a single private int size counter forces atomic CAS contention across all CPU cores.

ConcurrentHashMap uses a striped counter algorithm similar to LongAdder.

Instead of updating a single integer variable, threads update separate CounterCell array slots based on their thread hash ID:

Thread 1 (Core 0) ---> updates CounterCell[0]
Thread 2 (Core 1) ---> updates CounterCell[1]
Thread 3 (Core 2) ---> updates CounterCell[2]

totalSize() = baseCount + Sum(CounterCell[0] + CounterCell[1] + ...)

Summing the counter cell values on demand computes total map size without slowing down concurrent writes.

---

Quick Summary

• Collections.synchronizedMap bottlenecks throughput by acquiring a single global lock.
• JDK 8+ ConcurrentHashMap uses lock-free CAS for empty buckets and fine-grained synchronized locks on individual bucket heads.
• volatile node references deliver zero-lock get() read operations.
• Striped CounterCell arrays eliminate CPU cache line contention during atomic size updates.

---

Series Conclusion

Over these 18 parts, we built Java’s Collections Framework from memory pointers up to concurrent lock-free hash maps:

1. Memory layouts & object headers (Part 01)
2. equals() and hashCode() contracts (Part 02)
3. MyArrayList dynamic resizing (Part 03)
4. MyLinkedList double pointer links (Part 04)
5. Iterators and fail-fast modCount (Part 05)
6. Stacks and Queues (Parts 06-08)
7. Hash maps, load factors, and treeification (Parts 09-12)
8. Binary Search Trees and Red-Black rotations (Parts 13-15)
9. Min-heap Priority Queues (Part 16)
10. Fail-safe Copy-on-Write and ConcurrentHashMap internals (Parts 17-18)

You now possess the foundational engineering models to choose, optimize, and debug high-performance Java collections in production systems.

References & Further Reading

1. Goetz, B., et al. (2006). Java Concurrency in Practice — Chapter 5: Producer-Consumer and Blocking Queues. Addison-Wesley.
2. OpenJDK Repository. OpenJDK 21 Source Code: java.util.concurrent.ArrayBlockingQueue. GitHub.
3. Lea, D. (2000). Concurrent Programming in Java (2nd Edition). Addison-Wesley.

---