Concurrent Hash Map

Per-bucket locking + CAS (Java 8 style). Threads inserting into different buckets run in parallel; threads hitting the same bucket serialize. Watch a lock-free CAS install into an empty bucket, a synchronized-on-head insert into a populated one, and a cooperative concurrent resize that transfers buckets behind ForwardingNode markers.

get: lock-free O(1) put: CAS or sync-head resize: cooperative tree-bin > 8 → O(log n)

Speed slow fast

Idle bucket

CAS in progress (lock-free)

Lock held (sync on head)

Freshly inserted node

ForwardingNode (resizing)

Buckets

Entries

Load factor

0.00

CAS ops

Locks taken

State

idle

table (old / current)

nextTable (resize target, 2× size)

Trace

Press Auto demo, or type a key and put. Empty bucket → lock-free CAS. Occupied bucket → synchronized on the first node. At load factor > 0.75 the map resizes by cooperatively transferring buckets to a 2× table.

Complexity

Operation	Avg	Worst (chain)	Worst (tree-bin)	Sync cost
get(k)	O(1)	O(n)	O(log n)	lock-free
put(k) — empty bucket	O(1)	O(1)	O(1)	1 CAS
put(k) — populated	O(1)	O(n)	O(log n)	sync(head)
remove(k)	O(1)	O(n)	O(log n)	sync(head)
resize	O(n) total	O(n)	O(n)	cooperative
size()	O(cells)	O(cells)	O(cells)	striped, approx

Operation Log

Reads (get) are always lock-free: nodes' fields are volatile, so a reader sees a consistent value with no lock — even during resize, where it follows the ForwardingNode into the new table. Inserts into distinct buckets never contend; only same-bucket inserts serialize on the head node.