skip to content

How does ConcurrentHashMap's Java 8+ concurrency model use CAS on empty bins and per-bin locking, and how does it differ from the older segmented design?

level: seniorimportance: should knowfreq 55%

answer

  1. Java 8+: one Node[] table, reads lock-free
  2. put on empty bin -> CAS (no lock); non-empty -> synchronized on head node
  3. List -> tree past 8 nodes, capacity 64+
  4. Resize is cooperative (threads help transfer)
  5. Old design = Segments + ReentrantLock (writers capped by segment count)

basics

~20 s

In Java 8+, the map is one big array of buckets. A put into an empty bucket uses a single atomic CAS instruction (no lock). Adding to a non-empty bucket locks just that bucket. Reads never lock. The old design instead split the map into a few fixed 'segments', each with its own lock.

solid answer

~50 s

Java 8+ ConcurrentHashMap is a single Node array (the table), still the design at JDK 27. Reads take no lock: a volatile read of the table, an acquire read of the slot, then volatile node fields. If the target bin is empty, put installs the new node with a single CAS on that array slot, with no lock. If the bin is non-empty, it synchronizes on the bin's head node, so only writers to that one bin contend. Bins are linked lists; an insert into a bin of 8 or more nodes makes it a red-black tree if the table has at least 64 slots, otherwise the table resizes. Resizing is cooperative: other threads can help transfer bins. The pre-Java-8 design used lock striping: Segments (default 16), each a ReentrantLock guarding its own small hash table, so write concurrency was capped at the segment count and memory overhead was higher.

go deeper

for a junior

Can state that CHM allows concurrent access and doesn't lock the whole map, without internal detail.

for a middle

Knows reads are lock-free and writes use fine-grained (per-bin) locking, and that an older version used segments.

for a senior

Explains CAS-on-empty-bin vs synchronized-on-head-node, treeification thresholds, cooperative resize, and contrasts with the Java 7 segmented/lock-striped design.

for a principal

Reasons about contention behavior (hot keys, resize cost, striped size counter), the memory/throughput trade-offs that motivated the Java 8 rewrite, and how internal changes preserved the public concurrency contract.

## Vocabulary first - **Bin / bucket:** one slot of the backing array; it holds all entries whose key hashes to that index. Within a slot, colliding entries form a **linked list** (or a tree). - **CAS (compare-and-set):** an atomic CPU instruction `CAS(location, expected, new)` that writes `new` only if `location` currently equals `expected`, and reports success/failure—all without a lock. It's the foundation of **lock-free** updates. - **volatile read:** a read that sees the latest write to that variable in the synchronization order and, through happens-before, everything that write published (JLS §17.4). - **Monitor / synchronized:** Java's intrinsic lock; `synchronized(obj)` lets one thread at a time into the block. ## Java 8+ design, as it stands in the JDK 27 source (describe this by default) The map is a **single `Node[] table`** (lazily allocated on first insert). Each `Node` holds a key, value, the key's hash, and a `next` pointer. **Reads (`get`)** acquire **no lock**. They do a volatile read of the table reference, read the bin's slot with an acquire read (`tabAt`, weaker than volatile but enough to see a published node fully built), and walk the list through `volatile` `next` and `val` fields. Because new nodes are published with CAS or release writes, readers see a fully built node without blocking, so reads of a list bin neither contend with each other nor wait for writers. A tree bin adds a wrinkle: a reader CASes a count into `TreeBin.lockState` to search the tree, and if a writer holds or awaits that state, walks the `next` pointers instead, so "readers need never block". The public Javadoc's wording is that retrievals "do not entail locking" and "generally do not block". **Writes (`put`/compute/…):** 1. Compute the bin index from the (spread) hash. 2. **If the bin is empty:** attempt to install the new node with a single **CAS** on that array slot. On success, done—**no lock taken**. On CAS failure (another thread won the race), retry the loop. 3. **If the bin holds a `ForwardingNode`:** a resize is moving it, so help with the transfer and retry on the new table. 4. **Otherwise:** `synchronized` on the **bin's head node**, re-check that it is still the head (retry if not), then insert/update within that list or tree. Only writers targeting the **same bin** contend; different bins proceed in parallel. On an empty bin, `computeIfAbsent` and `compute` instead CAS in a placeholder `ReservationNode` and hold its monitor while the function runs, so other updates to that bin wait for it. **Treeification:** when an insert finds a bin already holding **8** or more nodes (so its list length exceeds 8) *and* the table capacity is at least **64**, the bin converts from a linked list to a **red-black tree**, bounding search at **O(log n)** instead of O(n) as long as keys are `Comparable` or have distinct hashes. Keys with identical hashes and no usable ordering can still force both subtrees to be searched. (If the table is small, it resizes instead of treeifying.) An insert is not the only trigger: the same check runs when `put`, `putIfAbsent`, `computeIfAbsent`, `compute` or `merge` finds its key at the 8th node or later, so a list of exactly 8 nodes can convert without growing. Bins shrink back to lists ("untreeify") when a resize split leaves 6 or fewer nodes, or when removals leave the tree too small. **Resizing is cooperative/concurrent:** when the table grows, **other threads can help** move bins from the old table to the new one (each claims a block of bins via a `transferIndex` CAS and takes each bin's lock, leaving a `ForwardingNode` behind so readers/writers find the new table). This shares the copying among threads, but the Javadoc still warns that a resize "may be a relatively slow operation". **Size counting:** to avoid a single hot counter, CHM uses a **striped counter** (`baseCount` + an array of `CounterCell`s, à la `LongAdder`). Consequently `size()`/`mappingCount()` are **estimates** under concurrent mutation, not exact snapshots. ## The older (Java 5–7) design: lock striping with Segments The map was an array of **`Segment`** objects (default **16**, the `concurrencyLevel`). Each `Segment` was itself a little hash table guarded by its **own `ReentrantLock`**. A write locked **the whole segment** containing the key; reads were mostly lock-free already. Consequences: - **Concurrency ceiling = number of segments.** With 16 segments, at most ~16 writers could proceed in parallel, regardless of table size. - **Higher memory overhead** (each segment is a separate structure). - Coarser locking: unrelated keys in the same segment still blocked each other. ## Why Java 8 changed it Per-bin granularity gives **much finer parallelism** (concurrency scales with table size, not a fixed segment count), **lower memory overhead** (no per-segment objects), and integrates cleanly with the new CAS-on-empty-bin fast path and treeification. JEP 270 records the switch: the implementation was "completely changed in June 2013" and "uses synchronized statements rather than ReentrantLock instances". Only a stripped-down `Segment` class survives, "for the sake of serialization compatibility". The contract carried over (retrievals without locking, weakly consistent iterators, no nulls), but Java 8 also added API: the `ConcurrentMap` compute family, the bulk operations and `mappingCount` are all `@since 1.8`. ## Practical implications to mention - A **hot key** still serializes through one bin's lock—per-bin locking helps spread load but doesn't eliminate contention on a single popular key. - `size()` is approximate under concurrency; don't build correctness on it. - Iterators are **weakly consistent** (a side effect of lock-free traversal): they never throw CME, traverse elements as they existed at construction exactly once, and may or may not reflect later changes. - The `concurrencyLevel` constructor arg is a sizing hint in Java 8+ (it raises the initial capacity to at least that value), not a hard segment count anymore.

  • What does concurrencyLevel mean in the Java 8+ constructor?
    It's now a sizing hint: the constructor raises the initial capacity to at least that value. It no longer fixes a number of independently lockable segments the way the pre-8 design did.
  • Why is size() only an estimate?
    Counting uses a striped LongAdder-style counter (baseCount + CounterCells) to avoid a single contended counter, so under concurrent mutation the sum reflects an approximate, racy total rather than a precise instantaneous snapshot.

  • Describing modern CHM as using Segments (that's pre-Java-8)
  • Saying writes lock the whole table
  • Claiming reads take a lock
  • Stating size() is exact under concurrent mutation
  • Saying treeify happens purely at length 8 ignoring the capacity-64 condition

CAS and per-bin locking, replacing segment locks
Java 1.8
ConcurrentHashMap
Java 1.5

Describes the design as it stands in the JDK 27 source. JEP 270 dates the rewrite to June 2013, for JDK 8, replacing ReentrantLock segments with synchronized on bin heads; no release note from 11 to 27 names this class.

context