ConcurrentHashMap (Java 8+)

Core operations and concurrency mechanisms. For comparisons, hash distribution, pitfalls, and iterators, see concurrenthashmap-reference.md.

Table of Contents

1. Architecture
2. initTable() — Lazy Initialization
3. get() — Lock-Free Read
4. put() — Per-Bin Write
5. TreeBin — Dual Structure and Read-Write Lock
6. transfer() — Cooperative Resize
7. remove()
8. addCount() — Element Counting and Resize Trigger
9. sizeCtl — Multi-Purpose Control Field
10. ForwardingNode — Resize Bridge

---

1. Architecture

ConcurrentHashMap
  └── volatile Node<K,V>[] table
        ├── bin[0]: null (empty)
        ├── bin[1]: Node → Node → Node (linked list, ≤8 nodes)
        ├── bin[2]: TreeBin → TreeNode ↔ TreeNode (red-black tree, >8 nodes)
        ├── bin[3]: ForwardingNode (resizing in progress)
        └── bin[N]: ...

Node Types

Type	Hash	Purpose
Node	≥ 0	Linked list node: hash, key, volatile val, volatile next
TreeNode	≥ 0	Red-black tree node (extends Node): adds parent, left, right, prev, red
TreeBin	-2	Container in table[i] that manages tree root + read-write lock
ForwardingNode	-1	Points to new table during resize
ReservationNode	-3	Placeholder during computeIfAbsent

Treeification Thresholds

• TREEIFY_THRESHOLD = 8 — list → tree when bin > 8 nodes
• UNTREEIFY_THRESHOLD = 6 — tree → list when bin < 6 nodes
• MIN_TREEIFY_CAPACITY = 64 — table must have ≥ 64 bins (otherwise resize instead)

2. initTable() — Lazy Initialization

Table is created on first put(). CAS on sizeCtl elects one thread to create it.

while ((tab = table) == null) {
    if ((sc = sizeCtl) < 0)
        Thread.yield();                    // another thread creating, back off
    else if (CAS(sizeCtl, sc, -1)) {       // claim init: positive → -1
        try {
            if ((tab = table) == null) {   // double-check
                table = new Node[n];       // volatile write
                sc = n - (n >>> 2);        // threshold = 0.75n
            }
        } finally {
            sizeCtl = sc;                  // restore threshold
        }
        break;
    }
}

Sequence Diagram

Thread A (winner)          sizeCtl              table              Thread B (loser)
     |                       |                    |                       |
     |--- CAS(16, -1) ----->|                    |                       |
     |    SUCCESS            |=-1                |                       |
     |                       |                    |          |--- read sizeCtl = -1
     |--- new Node[16] ---->|                    |          |--- yield() → loop
     |--- table = nt ------>|               =Node[16]       |
     |--- sizeCtl = 12 ---->|=12                 |          |--- table != null → done
     |--- done              |                    |                       |

If Thread A crashes after CAS but before creating the table, the finally block restores sizeCtl to positive, allowing other threads to retry.

3. get() — Lock-Free Read

Entirely lock-free. No CAS, no synchronized, just volatile reads.

Sequence Diagram

get(key)
     |
     |--- h = spread(key.hashCode())
     |--- e = tabAt(tab, (n-1) & h)          // volatile read
     |
     |--- [e == null?] → return null
     |
     |--- [e.hash == h && key match?]         // PATH 1: direct hit O(1)
     |    → return e.val
     |
     |--- [e.hash < 0?]                       // PATH 2: special node
     |    |--- TreeBin (hash=-2):
     |    |    |--- [no writer?] → CAS read lock → tree search O(log n)
     |    |    |--- [writer active?] → linked list fallback O(n)
     |    |--- ForwardingNode (hash=-1):
     |    |    → redirect to new table, search there
     |
     |--- while (e = e.next)                  // PATH 3: linked list O(n)
     |    → return e.val if match
     |
     |--- return null

Why get() Is Safe Without Locks

• table is volatile → sees latest array
• tabAt() uses Unsafe.getObjectVolatile() → sees latest bin head
• Node.val and Node.next are volatile → traversal sees latest values
• Writers use synchronized + volatile writes → changes are visible to readers

4. put() — Per-Bin Write

Sequence Diagram

put(key, value)
     |
     |--- [table == null?] → initTable() → retry
     |
     |--- f = tabAt(tab, (n-1) & h)
     |
     |=== Empty bin (f == null) ===
     |--- CAS(tab[i], null, new Node) → done (no lock)
     |
     |=== ForwardingNode (f.hash == -1) ===
     |--- helpTransfer() → retry on new table
     |
     |=== Linked list (f.hash >= 0) ===
     |--- synchronized(f) {
     |        double-check: tabAt(tab, i) == f ?
     |        traverse list:
     |          key exists → update val
     |          e.next == null → e.next = new Node (tail append)
     |    }
     |--- [binCount >= 8?] → treeifyBin()    // OUTSIDE synchronized
     |
     |=== TreeBin (f instanceof TreeBin) ===
     |--- synchronized(f) {
     |        putTreeVal():
     |          tree search O(log n)
     |          key exists → return node (caller updates val)
     |          insert: new TreeNode(next=first) → first = x (head prepend)
     |          lockRoot() → balanceInsertion() → unlockRoot()
     |    }
     |
     |=== After all paths ===
     |--- addCount(1) → maybe trigger/join resize

Key Design Decisions

• Empty bin: CAS (single pointer swap, no lock needed)
• Non-empty bin: synchronized(f) (compound operation: traverse + insert/update)
• Linked list: tail-append (already at tail after traversal)
• TreeBin: head-prepend (tree search doesn’t visit list tail, O(1) prepend)
• treeifyBin() outside synchronized — it acquires its own lock internally

5. TreeBin — Dual Structure and Read-Write Lock

Dual Structure: Tree + Linked List

Every TreeNode participates in both structures simultaneously:

table[i] → TreeBin (hash=-2, manages lock)
              │
              ├── Tree (root → left/right/parent):     for O(log n) writes
              │         D
              │        / \
              │       B   F
              │      / \
              │     A   C
              │
              ├── List (first → next):                  for lock-free reads
              │   first → A → B → C → D → F → null
              │
              └── lockState: 0                          read-write lock

• Tree pointers (left, right, parent) are NOT volatile — only accessed under lock
• List pointers (next) ARE volatile — accessed by lock-free readers
• first is volatile — readers start traversal here

Read-Write Lock (lockState)

WRITER = 1 (bit 0)    WAITER = 2 (bit 1)    READER = 4 (bit 2+, each reader adds 4)

lockState = 0   → nobody
lockState = 4   → 1 reader
lockState = 8   → 2 readers
lockState = 1   → writer active
lockState = 6   → 1 reader + writer waiting (4+2)

TreeBin.find() — Reader Path

find(h, key):
  [writer active?] → linked list fallback O(n), NO lock needed
  [no writer?]     → CAS(+READER) → tree search O(log n) → CAS(-READER)
                     if last reader + waiter → unpark writer

Readers NEVER block. They either use the fast tree path or fall back to the linked list.

lockRoot() — Writer Path

lockRoot():
  CAS(0, WRITER) → success? done
  contendedLock():
    loop:
      (s & ~WAITER) == 0?  → CAS to WRITER (no readers, ignoring own WAITER bit)
      (s & WAITER) == 0?   → set WAITER bit, register as waiting
      waiter == me?         → park (sleep until last reader unparks)

(s & ~WAITER) == 0 means “no readers and no writer, ignoring the WAITER bit I set myself.”

Only one writer waits at a time — synchronized(bin) in put() serializes writers before they reach lockRoot().

6. transfer() — Cooperative Resize

Multiple threads migrate bins in parallel. Each claims a stride (min 16 bins).

Sequence Diagram

transfer(tab, nextTab)
     |
     |--- nextTab = new Node[2 * tab.length]
     |--- stride = max(16, (n/8)/NCPU)
     |
     |--- for each bin (counting down):
     |    |
     |    |--- [null bin?] → CAS ForwardingNode → advance
     |    |--- [ForwardingNode?] → already done → advance
     |    |--- [has nodes?]
     |         |--- synchronized(f) {
     |         |      split into lo-chain (stays) + hi-chain (moves to i+n)
     |         |      using (hash & n) == 0 test
     |         |      setTabAt(nextTab, i, loHead)
     |         |      setTabAt(nextTab, i+n, hiHead)
     |         |      setTabAt(tab, i, ForwardingNode)  // mark done
     |         |    }
     |
     |--- CAS(sizeCtl, sc, sc-1)              // exit
     |--- [last thread?] → table = nextTab    // THE SWAP

Bin Splitting

Old table (size 16), bin[5]: A(5) → B(21) → C(37) → D(53)

Test: hash & 16 (the new high bit)
  A: 5  & 16 = 0  → lo (stays at bin[5])
  B: 21 & 16 = 16 → hi (moves to bin[21])
  C: 37 & 16 = 0  → lo
  D: 53 & 16 = 16 → hi

New table (size 32):
  bin[5]:  A → C    (lo chain)
  bin[21]: B → D    (hi chain)

Two Paths to Join Transfer

Thread Action	Joins Transfer?	Via
put() hits ForwardingNode	Yes	helpTransfer() in put loop
put() into normal bin	Yes	addCount() after insert
get() hits ForwardingNode	No	Just redirects via find()

7. remove()

remove(key)
     |
     |--- [ForwardingNode?] → helpTransfer() → retry
     |
     |--- synchronized(f) {
     |        Linked list: unlink by updating pred.next
     |        TreeBin: removeTreeNode()
     |          → unlink from list (prev/next)
     |          → lockRoot() → remove from tree + rebalance → unlockRoot()
     |          → [< 6 nodes?] → untreeify back to linked list
     |    }
     |--- addCount(-1)

8. addCount() — Element Counting and Resize Trigger

Uses striped counters (same algorithm as LongAdder) to avoid CAS bottleneck:

Total count = baseCount + sum(counterCells[i].value)

Flow

addCount(1):
  Try CAS on baseCount (fast path)
    → fail? Hash thread → CAS on counterCells[i]
      → fail? fullAddCount() retry loop (expand cells if needed)

  Then check resize:
    sizeCtl >= 0 && count > sizeCtl → initiate new resize
    sizeCtl < -1                    → join existing resize

CounterCell

@Contended  // padding to avoid false sharing
static final class CounterCell {
    volatile long value;
}

Array grows up to NCPU. size() sums all cells — approximate under concurrency.

9. sizeCtl — Multi-Purpose Control Field

sizeCtl value          Meaning
─────────────          ───────
-1                     Table being initialized
< -1                   Resize in progress (upper 16 bits = stamp, lower 16 = thread count + 1)
0                      Not yet initialized
> 0                    Next resize threshold (capacity × 0.75)

During Resize: Stamp + Thread Count

sizeCtl = (resizeStamp(n) << 16) + 2    // 1 active thread
stamp + 3 = 2 threads, stamp + 4 = 3 threads, ...
Last thread: (sc - 2) == stamp << 16 → performs table = nextTab

The stamp is derived from old table size via Integer.numberOfLeadingZeros(n) | (1 << 15). Bit 15 ensures sizeCtl is negative when shifted left 16 (sign bit set).

10. ForwardingNode — Resize Bridge

Sentinel placed in old table after a bin is migrated:

static final class ForwardingNode<K,V> extends Node<K,V> {
    final Node<K,V>[] nextTable;
    ForwardingNode(Node<K,V>[] tab) {
        super(MOVED, null, null);  // hash = -1
        this.nextTable = tab;
    }
}

Lifecycle

Phase 1: bin[i] = Node → Node → Node           (normal)
Phase 2: synchronized → split → write to nextTab (migrating)
Phase 3: bin[i] = ForwardingNode → nextTab       (done, redirects)
Phase 4: table = nextTab → ForwardingNodes GC'd  (swap complete)

How Operations Handle It

• get(): calls ForwardingNode.find() → searches new table (lock-free)
• put(): calls helpTransfer() → migrates some bins → retries on new table
• put() into non-migrated bin: proceeds normally on old table, joins resize via addCount()

Ordering is critical: ForwardingNode is set AFTER entries are in the new table. Otherwise get() would follow it to an empty table.

---

Node Reuse During Bin Splitting

During transfer(), most nodes are created NEW, but a tail run of consecutive same-destination nodes is REUSED.

// Phase 1: Find last run of nodes all going to the same chain
int runBit = fh & n;
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
    int b = p.hash & n;
    if (b != runBit) { runBit = b; lastRun = p; }
}
// lastRun → ... → null all share the same destination → REUSE them

// Phase 2: Create NEW nodes for everything before lastRun
for (Node<K,V> p = f; p != lastRun; p = p.next) {
    if ((p.hash & n) == 0)
        ln = new Node<>(p.hash, p.key, p.val, ln);  // NEW, prepend to lo
    else
        hn = new Node<>(p.hash, p.key, p.val, hn);  // NEW, prepend to hi
}

Example:

Original: A(lo) → B(hi) → C(lo) → D(hi) → E(hi) → F(hi)
                                   ^^^^^^^^^^^^^^^^^^^^^^^^
                                   last run: D,E,F all hi → REUSE

Result:
  lo: new(A) → new(C)              (2 new nodes)
  hi: new(B) → D → E → F          (1 new + 3 reused)

Old table chain: A → B → C → D → E → F  ← INTACT for in-flight get() readers

Why new nodes? Concurrent get() may still be traversing the old chain via next pointers. Mutating next on existing nodes would break in-flight readers. New nodes for the new table leave the old chain intact.

Why reuse the tail run? Those nodes’ next pointers already form the correct chain for their destination — no mutation needed, safe to share.

Table of Contents

• Java 7 vs Java 8+ Comparison
• vs Guava LoadingCache
• Hash Distribution and spread()
• Why spread() Uses & HASH_BITS
• Maximum Table Capacity
• Table Never Shrinks
• Weakly Consistent Iterators
• Common Pitfalls
• Why synchronized Instead of CAS for Writes

---

Java 7 vs Java 8+ Comparison

Aspect	Java 7	Java 8+
Structure	Segment[16] → HashEntry[]	Node[] flat array
Locking	Per-segment ReentrantLock	Per-bin synchronized on first node
Read locking	Lock-free (volatile)	Lock-free (volatile)
Collision handling	Linked list only	Linked list → red-black tree
Worst-case lookup	O(n)	O(log n) after treeification
Resize	Per-segment	Cooperative multi-thread transfer
computeIfAbsent	Not available	Built-in, per-bin atomic
concurrencyLevel	Controls segment count	Ignored (kept for compatibility)
Memory overhead	Higher (segment objects)	Lower (no segment layer)

vs Guava LoadingCache

Feature	ConcurrentHashMap	Guava LoadingCache
Thread-safe	✅	✅
Lock-free reads	✅ (volatile)	✅ (volatile)
Per-key locking	✅ (per-bin)	✅ (per-segment)
Auto-load on miss	❌ (manual computeIfAbsent)	✅ (CacheLoader.load())
TTL / Expiration	❌	✅ (expireAfterWrite/Access)
Max size eviction	❌	✅ (maximumSize)
Statistics	❌	✅ (recordStats())
Treeification	✅ (Java 8+)	❌ (linked list only)
Cooperative resize	✅	❌

Use ConcurrentHashMap for a simple thread-safe map without eviction. Use Guava LoadingCache for TTL, size limits, and auto-loading.

Hash Distribution and spread()

How Bin Index Is Computed

int i = (table.length - 1) & spread(key.hashCode());

Keys in the same bin have the same masked index, not necessarily the same hashCode().

The spread() Function

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;  // HASH_BITS = 0x7fffffff
}

XORs upper 16 bits into lower 16 bits so bin indexing uses information from the entire hash.

Original hash:     AAAA_AAAA_BBBB_BBBB_CCCC_CCCC_DDDD_DDDD
Shifted right 16:  0000_0000_0000_0000_AAAA_AAAA_BBBB_BBBB
XOR result:        AAAA_AAAA_BBBB_BBBB_(C^A)(C^A)(D^B)(D^B)
                                        ^^^^^^^^^^^^^^^^^^^^^^^^
                                        lower bits now carry info from BOTH halves

Why hashCode() Often Has Upper-Bit Variation

1. 31 * hash + field pattern shifts bits left each iteration
2. Composite object hashing pushes early fields into upper bits
3. Float.hashCode() returns IEEE 754 bits — small floats share exponents
4. Sequential integer multiples of powers of 2 share identical lower bits

Sequential Integer Keys: Nuance

Plain sequential integers (1, 2, 3) distribute fine. The problem is sequential multiples of a power of 2:

 0 & 0xF = 0,  16 & 0xF = 0,  32 & 0xF = 0,  48 & 0xF = 0

For small integers, spread() has limited effect because upper 16 bits are all zeros. The real benefit kicks in with larger values.

Why spread() Uses & HASH_BITS

HASH_BITS = 0x7fffffff clears the sign bit, ensuring spread hash is always non-negative.

Negative hashes are reserved for special node types:

Hash Value	Constant	Node Type
-1	MOVED	ForwardingNode
-2	TREEBIN	TreeBin
-3	RESERVED	ReservationNode

If a regular key’s spread hash were negative, it would be misidentified as a special node.

Since max table size is 1 << 30, bit 31 never participates in bin selection anyway — no distribution is lost.

Maximum Table Capacity

private static final int MAXIMUM_CAPACITY = 1 << 30;  // 1,073,741,824

• 1 << 31 produces Integer.MIN_VALUE (negative) — breaks bin indexing
• Integer.MAX_VALUE is not a power of 2 — breaks bitmask trick
• In practice, OOM long before reaching this limit

Table Never Shrinks

ConcurrentHashMap only grows, never shrinks. Removing entries does not reduce table size.

• Empty bins cost only 4-8 bytes each (null references)
• Shrinking would require full table migration (same complexity as growing)
• To reclaim memory: create a new smaller map and copy entries

Note: untreeify (tree → list when bin < 6 nodes) changes bin structure, not table size.

Weakly Consistent Iterators

Iterators never throw ConcurrentModificationException but may not reflect all concurrent modifications.

The Guarantee

1. Every element present when iterator was created AND remains throughout WILL be returned
2. No element returned more than once
3. Elements added/removed during iteration MAY or MAY NOT be reflected

During Resize

Iterator follows ForwardingNode to new table transparently. May see some entries from old table, some from new.

Practical Advice

// Safe — no exception, may miss concurrent additions
for (Map.Entry<K,V> entry : map.entrySet()) { process(entry); }

// For consistent snapshot, copy first
Map<K,V> snapshot = new HashMap<>(map);
for (Map.Entry<K,V> entry : snapshot.entrySet()) { process(entry); }

Node Deletion During Iteration

Iterator position	Sees deleted node?	Why
Past deleted node	Yes (stale)	Already traversed it
At deleted node	Yes (stale)	Holding reference; node.next still valid
At predecessor	Maybe	Race on volatile read
Before predecessor	No	By arrival time, next chain skips it

Common Pitfalls

1. Don’t use putIfAbsent + get — use computeIfAbsent

// Bad — expensiveCreate() runs even if key exists
map.putIfAbsent("key", expensiveCreate());

// Good — function only called if key absent
map.computeIfAbsent("key", k -> expensiveCreate());

2. Don’t call computeIfAbsent recursively on the same map

// DEADLOCK if A and B hash to same bin
map.computeIfAbsent("A", k -> map.computeIfAbsent("B", k2 -> value));

3. size() is approximate under concurrency

int size = map.size();           // approximate, capped at Integer.MAX_VALUE
long count = map.mappingCount(); // preferred for large maps

4. Iterators are weakly consistent

See “Weakly Consistent Iterators” section above.

Why synchronized Instead of CAS for Writes

CAS works for empty bins (single pointer: null → Node). Non-empty bins require compound operations (traverse + check + insert/update + maybe treeify) that CAS can’t cover atomically.

Modern JVM optimizes synchronized heavily:

Optimization	What It Does
Biased locking	Nearly zero overhead for single-thread access
Lightweight lock	CAS-based fast path for low contention
Adaptive spinning	Spins before parking to avoid context switch
Lock coarsening	JIT merges adjacent synchronized blocks

Scenario	Mechanism	Why
Empty bin	CAS	Single pointer swap
Non-empty bin	synchronized	Multi-step traversal + mutation
Resize	CAS + synchronized	CAS claims bins, synchronized moves nodes

Key, Value, and hashCode Relationship

Relationship	Same hashCode()?	Same bin?
Same key (equals true)	Yes (Java contract)	Yes
Different keys, same value	No guarantee	No guarantee
Different keys, same hashCode (collision)	Yes	Yes
Different keys, different hashCode, same masked index	No	Yes (bin collision)

Connection to Other Docs

• concurrenthashmap-internals.md — Core operations (get/put/resize/TreeBin)
• java-volatile-and-memory-model.md — volatile, happens-before, double-checked locking
• java-thread-internals.md — Thread lifecycle, synchronization primitives, thread pools

Unsafe Array Access: Per-Element Volatile Semantics

Java’s volatile on an array reference only makes the pointer volatile, not the elements:

volatile Node<K,V>[] table;  // volatile = the REFERENCE to the array
                              // table[0], table[1], ... are NOT volatile

ConcurrentHashMap uses sun.misc.Unsafe to get per-element volatile semantics:

The Three Array Access Methods

// Volatile read of tab[i]
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

// Volatile write to tab[i]
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
    U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}

// Atomic CAS on tab[i]
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

((long)i << ASHIFT) + ABASE computes the raw byte offset of element tab[i] in memory.

Memory Semantics

Method	Read	Write	Atomic?	CPU Instruction
tabAt (getObjectVolatile)	Volatile (load barrier)	—	Single read	Load fence
setTabAt (putObjectVolatile)	—	Volatile (store barrier)	Single write	Store fence
casTabAt (compareAndSwapObject)	Volatile	Volatile	Read+compare+write	LOCK CMPXCHG (x86)

CAS provides full memory barrier — equivalent to volatile read + volatile write + atomicity, all in one CPU instruction.

Why Not Just volatile Elements?

Java doesn’t support volatile array elements. You can’t declare volatile Node[] and have table[i] be volatile. Unsafe is the workaround.

In Java 9+, VarHandle replaces Unsafe with a safer API:

private static final VarHandle AHANDLE = MethodHandles.arrayElementVarHandle(Node[].class);
Node<K,V> n = (Node<K,V>)AHANDLE.getVolatile(tab, i);