Java ConcurrentHashMap Internal Working with CAS and Stripes

Introduction

The Java ConcurrentHashMap class was added in Java 5 (2004) as part of JSR 166. The original Java 5 implementation partitioned the map into a fixed number of segments, each of which was a small Hashtable with its own lock. This segment-striped design allowed up to 16 concurrent writers (the default segment count) without contention. Java 8 (2014) rewrote the internals to use per-bin locking with compare-and-swap on the bin head, eliminating the segment array entirely while preserving the thread-safety contract. The java concurrenthashmap internal design is one of the most studied lock-stripping data structures in computer science, and it is the foundation of every high-throughput Java cache.

For a Java learner, understanding the internal machinery of ConcurrentHashMap unlocks the door to writing concurrent data structures in general. The Java 8 design shows how CAS operations (provided by sun.misc.Unsafe in Java 8 and java.lang.invoke.VarHandle in Java 9+) can be combined with fine-grained locking to allow thousands of readers and dozens of writers to share the same map with minimal contention. This post walks through the segment design, the bin-striped design, the bin-invalidation technique for tree fallbacks, and the count semantics.

What is Java ConcurrentHashMap Internal Working?

The java concurrenthashmap internal design is a hash-table implementation that supports fully concurrent reads and a configurable level of concurrent writes. Reads never take a lock; they walk the bin array using volatile reads and use a sentinel value (MOVED in Java 8) to detect bins that are being resized, in which case the reader helps with the transfer. Writers synchronise on the first node of a bin (the bucket head), so writers working on different bins do not contend with each other.

ConcurrentHashMap belongs to the family of lock-striped hash maps, alongside the older Hashtable (which locks the entire table) and HashMap (which is not thread-safe at all). It is distinct from Collections.synchronizedMap around a HashMap (which uses a single coarse-grained lock and serialises everything). It is also distinct from ConcurrentSkipListMap, which uses a skip list rather than a hash table and supports ordered iteration.

How Java ConcurrentHashMap Internal Working Works - Step by Step

Step 1: The bin array. The internal table is a volatile array of Node references. Each Node has an int hash, a volatile K key, a volatile V value, and a volatile Node next. The hash code of a key is perturbed by spreading its high bits into the low bits (the same trick HashMap uses) to reduce collisions when keys share low-order bits.

Step 2: A get(key) call reads the volatile bin array, computes the bin index, and walks the linked list at that bin. The walk uses only volatile reads, so no lock is taken and no wait is imposed on writers. If the bin head is a ForwardingNode (with hash value MOVED = -1), the reader is in the middle of a resize and helps transfer bins to the new table before continuing.

Step 3: A put(key, value) call computes the bin index and tries a CAS on the bin head if the bin is empty, installing a new Node atomically. If the bin is non-empty, the writer synchronises on the bin head (synchronized on the first Node) and walks or extends the linked list. Synchronising on the bin head means that two writers in different bins do not contend.

Step 4: When a bin grows beyond a threshold (default 8 nodes), the linked list is converted to a TreeBins red-black tree. The conversion happens under the bin lock. TreeBins gives O(log n) lookup on the worst-case bin instead of O(n), which protects the map against hash-collision attacks.

Step 5: Resizing. When the total size exceeds the load factor times the capacity, a new bin array (twice the size) is allocated. The resize is parallel: each thread that helps transfers one bin at a time from the old array to the new array, replacing the old bin head with a ForwardingNode so subsequent operations on the old bin redirect to the new table. The resize completes when all bins have been transferred.

Java Program for ConcurrentHashMap Internal Working

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;

public class ConcurrentHashMapInternalDemo {
    public static void main(String[] args) throws InterruptedException {
        ConcurrentHashMap<String, AtomicLong> counts = new ConcurrentHashMap<>();
        ExecutorService pool = Executors.newFixedThreadPool(8);

        int tasksPerWorker = 100_000;
        int workers = 8;
        for (int t = 0; t < workers; t++) {
            final int seed = t;
            pool.submit(() -> {
                for (int i = 0; i < tasksPerWorker; i++) {
                    String key = "k" + ((seed + i) % 16);
                    // atomic point-in-time update via compute
                    counts.compute(key, (k, v) -> {
                        if (v == null) v = new AtomicLong(0);
                        v.incrementAndGet();
                        return v;
                    });
                }
            });
        }
        pool.shutdown();
        pool.awaitTermination(10, TimeUnit.SECONDS);

        long total = 0;
        for (AtomicLong c : counts.values()) total += c.get();
        System.out.println("distinct keys  = " + counts.size());
        System.out.println("total counters = " + total);
        for (var e : counts.entrySet()) {
            System.out.println("  " + e.getKey() + " = " + e.getValue());
        }

        // Demonstrate the atomic putIfAbsent and replace patterns
        AtomicLong slot = counts.putIfAbsent("k0", new AtomicLong(999));
        System.out.println("putIfAbsent returned existing? " + (slot != null));
        System.out.println("k0 final value = " + counts.get("k0"));
    }
}

Code Explanation - Line by Line

The main method constructs a ConcurrentHashMap whose values are AtomicLong counters. The map is the stripe set; each key maps to one counter that the writer threads increment. The pattern of one AtomicLong per key inside a ConcurrentHashMap is a common idiom for stripe-counting, because it combines the lock-free map access (no contention between threads in different bins) with the atomic counter increment (no contention between threads in the same bin, modulo the AtomicLong CAS).

The thread pool spins up 8 workers, each running 100,000 increment tasks. The keys cycle through 16 distinct strings (k0 through k15) so that each worker touches all 16 bins but does so in a different interleaving. The compute method takes a BiFunction that receives the current value (or null) and returns the new value. The compute method holds the bin lock for the duration of the function, so the read-modify-write of the AtomicLong is atomic with respect to other writers on the same bin.

The shutdown and awaitTermination sequence ensures the pool has finished before the main thread reads the totals. Without the await, the totals would be partial. The 10-second timeout is generous for a workload that should finish in well under a second.

The iteration over counts.values() at the end is a weakly consistent iterator. It does not throw ConcurrentModificationException, and it visits only the bins that existed at iterator creation time. If another thread were modifying the map during the iteration, the iterator might see some new entries and miss others; the guarantee is that the iterator visits at least the entries that were present when it started.

The putIfAbsent call at the very end demonstrates the CAS-style atomic insertion. The map returns the existing value (the AtomicLong that was already inserted by the workers) instead of null, so the call did not change the map. The toString of an AtomicLong shows its current long value, so the println reflects the final tally after the workers have finished.

Sample Input and Output

Input:
  8 worker threads each doing 100,000 increments
  16 distinct keys (k0 through k15)
  Total increments expected: 8 x 100,000 = 800,000

Output (final lines):
  distinct keys  = 16
  total counters = 800000
    k0 = 50000
    k1 = 50000
    k2 = 50000
    k3 = 50000
    k4 = 50000
    k5 = 50000
    k6 = 50000
    k7 = 50000
    k8 = 50000
    k9 = 50000
    k10 = 50000
    k11 = 50000
    k12 = 50000
    k13 = 50000
    k14 = 50000
    k15 = 50000
  putIfAbsent returned existing? true
  k0 final value = 50000

The total counters is exactly 800,000, which confirms that the compute method provided the necessary atomicity for the read-modify-write of the AtomicLong counter. Each key ends with 50,000 because the eight workers each touch every key in a different interleaving; modulo-16 distribution puts exactly 50,000 increments into each of the 16 keys. The putIfAbsent call returned the existing AtomicLong (truthy), so the new AtomicLong(999) was discarded and the k0 final value is 50,000.

Common Mistakes to Avoid

Mistake 1: Using ConcurrentHashMap.get and ConcurrentHashMap.put in sequence to implement an atomic check-then-act. Two separate calls are not atomic; a writer can sneak in between them. Use computeIfAbsent, compute, or merge for atomic read-modify-write inside a single bin-lock-protected call.

Mistake 2: Iterating over keySet() and modifying the map during iteration. The weakly consistent iterator does not throw ConcurrentModificationException, but it also does not reflect new entries reliably. If you need a stable snapshot, copy the entries into a list first using new ArrayList(map.entrySet()) and iterate over that list.

Mistake 3: Assuming null keys or null values are allowed. ConcurrentHashMap forbids both, throwing NullPointerException on put(null, x) or put(x, null). The reason is that the ambiguity of null in the return value of get cannot be disambiguated cleanly in a concurrent setting, where the absence of a key at one moment does not mean it will be absent the next.

Mistake 4: Computing size() frequently in performance-critical code. The size is maintained as a sum of striped counters that are summed on demand, so size() is O(number of stripes) and can be slow under heavy contention. Use isEmpty() when you only need the zero-or-non-zero answer, or maintain your own AtomicLong if you need size in a hot loop.

Real-World Applications

ConcurrentHashMap is the backbone of every Java cache. The Guava Cache implementation builds on ConcurrentHashMap for the storage layer. Caffeine (the de-facto modern Java cache) uses a modified ConcurrentHashMap with a Clock-PRO eviction policy bolted on. Spring's @Cacheable uses ConcurrentHashMap as the default in-memory cache backend. The pattern is universal: read-heavy, write-rare, atomically-updateable storage.

Application configuration registries. Spring's ApplicationContext uses a ConcurrentHashMap for bean definitions. The Eclipse MicroProfile Config implementation uses a ConcurrentHashMap for the source map. Anywhere a framework needs to look up a small map of beans or properties by name from many threads, ConcurrentHashMap is the answer.

Java's own standard library uses ConcurrentHashMap internally. The String intern table in HotSpot uses a striped variant. The ThreadLocalRandom implementation uses stripes. The java.util.ServiceLoader cache is a ConcurrentHashMap. The dependency on this single class is one reason the Java ecosystem scales to tens of thousands of threads per JVM.

Distributed-system client libraries use ConcurrentHashMap for connection pools, channel maps, and subscription tables. gRPC Java uses ConcurrentHashMap for the stream registry. Apache Kafka's client uses ConcurrentHashMap for the topic-partition metadata. The reason is the same as everywhere else: the access pattern is read-heavy with occasional writes, and the cost of a striped data structure is dwarfed by the network cost it supports.

Conclusion

The java concurrenthashmap internal design is a per-bin locked hash table with CAS on the bin head for empty bins and a ForwardingNode protocol for parallel resize. Readers take no locks; writers lock only the bin they are mutating. To go further, study ConcurrentSkipListMap for the ordered analogue and ConcurrentLinkedHashMap (or Caffeine) for an LRU-bounded variant.