Explain ConcurrentHashMap's internal concurrency model in Java 8+: CAS on empty bins, per-bin locking, and how it differs from the older segmented design.
answer
- Java 8+: one Node[] table, reads lock-free
- Empty bin -> CAS install (no lock); non-empty -> synchronized on head node
- Bin list -> red-black tree at length 8 & capacity 64
- Resize is cooperative (threads help transfer)
- Old design = fixed Segments + ReentrantLock (concurrency capped at ~16)
basics
~20 sIn Java 8+, the map is one big array of buckets. Adding the first entry to 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 sJava 8+ ConcurrentHashMap is a single Node array (the table). Reads are lock-free via volatile reads of the table and node references. On a write, if the target bin is empty, it inserts the new node with a single CAS (compare-and-set) on that array slot—no lock acquired. If the bin is non-empty, it synchronizes on the bin's head node, so only writers to that one bin contend; other bins proceed in parallel. Bins are linked lists, but once a bin grows past a threshold (8) and the table is large enough, it 'treeifies' into a red-black tree for O(log n) worst-case lookup. Resizing is cooperative: multiple threads help transfer bins concurrently. The pre-Java-8 design used lock striping: a fixed array of Segments (default 16), each a small hash table with its own ReentrantLock, so concurrency was capped at the segment count and memory overhead was higher. Java 8 moved to per-bin granularity, giving finer parallelism and lower footprint.
go deeper
Can state that CHM allows concurrent access and doesn't lock the whole map, without internal detail.
Knows reads are lock-free and writes use fine-grained (per-bin) locking, and that an older version used segments.
Explains CAS-on-empty-bin vs synchronized-on-head-node, treeification thresholds, cooperative resize, and contrasts with the Java 7 segmented/lock-striped design.
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 with memory-visibility guarantees, so a value written by another thread is seen promptly and not from a stale cache. - **Monitor / synchronized:** Java's intrinsic lock; `synchronized(obj)` lets one thread at a time into the block. ## Java 8+ design (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, index into the bin with a volatile read of the slot, and walk the list/tree. Because publication of new nodes uses volatile/CAS writes, readers see a consistent-enough view without blocking. This is why reads scale linearly with cores. **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 is non-empty:** `synchronized` on the **bin's head node**, then insert/update within that list or tree. Only writers targeting the **same bin** contend; different bins are fully parallel. **Treeification:** if a single bin's 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 worst-case lookup at **O(log n)** instead of O(n). (If the table is small, it resizes instead of treeifying.) Bins shrink back to lists ("untreeify") when small. **Resizing is cooperative/concurrent:** when the table grows, **multiple threads help** move bins from the old table to the new one (each claims a stride of bins via a `transferIndex` CAS, leaving a `ForwardingNode` behind so readers/writers find the new table). This avoids the single-thread resize stalls and the infamous **pre-Java-8 HashMap concurrent-resize infinite loop**. **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. The visible behavioral contracts (lock-free reads, weakly consistent iterators, no nulls, atomic compound methods) stayed the same; only the internals changed. ## 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): never throw CME, reflect some valid past/ongoing state. - The `concurrencyLevel` constructor arg is largely a legacy/sizing hint in Java 8+, not a hard segment count anymore.
- What does concurrencyLevel mean in the Java 8+ constructor?It's now mostly a sizing/contention hint used to pre-size internal structures; it no longer fixes a hard 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.
saying these in an interview costs you the question
- 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