ConcurrentHashMap Internals

ConcurrentHashMap is a thread-safe map that allows concurrent reads and high concurrency for writes by partitioning the table into segments (Java 7) or using CAS and synchronized on per-bucket (or tree) nodes (Java 8+). This article explains the Java 8+ design: array of nodes, CAS for empty bins, synchronized for the head of a bin, and treeification when lists are long.

Overview

• No global lock: Reads do not block each other; writes lock only the affected bin (bucket) or use CAS for empty bins. So concurrency is much higher than a single lock (e.g. Collections.synchronizedMap).
• Structure (Java 8+): Table is an array of nodes. Each node is a list (or tree) head. Hash determines the bin; put/get only touch that bin (and possibly the table reference during resize).
• CAS: For inserting into an empty bin, use CAS to set the first node; no lock. For updating an existing node or inserting into a non-empty list, synchronize on the bin head.
• Tree: When a list in one bin exceeds a threshold (e.g. 8) and table is large enough, the list is converted to a red-black tree to keep operations O(log n). Shrinking can convert back to list.

Example

Example 1: Safe concurrent put and get

JavaCopy
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("a", 1);
map.put("b", 2);
Integer v = map.get("a");  // 1, no lock needed
map.compute("a", (k, val) -> val == null ? 1 : val + 1);  // atomic update per key

• get is lock-free (volatile read of table and node values). put/compute use lock per bin so different keys can proceed in parallel.

Example 2: Bulk operations

JavaCopy
map.forEach((k, v) -> ...);           // does not lock entire map; snapshot semantics are weak
map.replaceAll((k, v) -> v + 1);      // updates in place per bin
map.computeIfAbsent("x", k -> expensive());  // only one thread wins for "x"; others may block on that bin

• forEach can see a concurrent modification; it is weakly consistent. computeIfAbsent runs the mapping function only if the key is absent; the bin is locked so only one thread computes for that key.

Example 3: Size and capacity

• size() is computed by summing per-bucket counts (or similar); it is approximate under concurrency. Table resizes when load factor is exceeded; resizing can be done by multiple threads (help transfer) or by the writing thread.

Core Mechanism / Behavior

• Hash and bin: Key’s hash is spread (e.g. spread(hashCode)) to reduce collisions. Index = (n - 1) & hash. Only that bin is locked for put/remove.
• Synchronized: The lock is the first node of the bin (or the bin object). So two threads updating different bins do not block each other.
• Resize: When the table grows, bins are split; some nodes stay in the old bin, some move to the new bin. Iterators and get can traverse while resize is in progress (help transfer or see old/new table).

Operation	Concurrency
get	Lock-free (volatile reads)
put (empty bin)	CAS
put (non-empty bin)	Synchronized on bin head
remove	Synchronized on bin head
size	Approximate (no global lock)

Key Rules

• Prefer ConcurrentHashMap over synchronized Map when you need high read/write concurrency. Do not lock on the map instance for application logic; use per-key or per-bin locking or use the provided atomic methods (compute, putIfAbsent, etc.).
• computeIfAbsent: the mapping function can be invoked more than once under contention (in theory); it should be side-effect free or idempotent. Prefer simple, fast lambdas.
• Iterators are weakly consistent: they can see updates after iteration started but do not throw ConcurrentModificationException. Do not assume a fully consistent snapshot.

What's Next

See Java Collections for HashMap vs ConcurrentHashMap. See AQS Explained for how other concurrent structures (e.g. locks) work. See JMM for visibility of updates.