The idea: lock a bin, not the map

A java.util.concurrent.ConcurrentHashMap has the same layout as a HashMap: an array of bins, each holding a linked list of nodes (or a tree). What it adds is a way for many threads to use the map at once without one big lock. Since JDK 8 it uses three tools:

  • CAS (compare-and-swap) to put the first node into an empty bin, with no lock at all;
  • synchronized on one bin (on its first node) to change a bin that already has nodes;
  • volatile reads so that get never needs a lock.

So two threads only wait for each other when they write to the same bin. With 8 bins and random keys that is rare; with thousands of bins it is very rare.

The canvas runs three threads, T1, T2 and T3, on one map. Each thread has a short script of calls. Time moves in ticks: in each tick every runnable thread does one small step, T1 first, then T2, then T3. A value a thread read in one tick can be out of date in the next, which is exactly what makes concurrent code hard. Each thread has one colour, used for its lane, the locks it holds, the nodes it wrote and the counter cell it adds to.

Add Random picks n different random keys from 0 to 99, deals them out to T1, T2 and T3 in turn as put calls, and runs the three threads together. With 8 bins, collisions are common, so most runs show CAS races, BLOCKED threads or CounterCells, and 6 or more new keys start a resize.

Insert into an empty bin: CAS, no lock

for (Node[] tab = table;;) {
    int i = (n - 1) & hash;
    Node f = tabAt(tab, i);                         // volatile read of the slot
    if (f == null) {
        if (casTabAt(tab, i, null, new Node(hash, key, value)))
            break;                                  // done, no lock taken
        // CAS failed: someone else filled the slot first. Loop and read again.
    }
    else if (f.hash == MOVED) tab = helpTransfer(tab, f);
    else synchronized (f) { ... }                   // see below
}
addCount(1L, binCount);

casTabAt writes the new node only if the slot still holds null, in one atomic CPU instruction (see Compare-and-Swap). In Demo 1: different bins all three threads insert into empty bins in the same tick, and nobody waits. In Demo 2: CAS race T1 and T2 both read an empty bin 1. T1's CAS wins. T2's CAS fails because the slot is no longer null, so T2 loops, reads the bin again, sees T1's node, and takes the locked path.

Change a non-empty bin: synchronized on its first node

If the bin has nodes, the thread enters synchronized (f), where f is the bin's first node. Only threads that want the same bin wait for this monitor; their state is BLOCKED. Inside the lock, the thread first checks tabAt(tab, i) == f. If the bin changed in the meantime (for example, a resize moved it), it unlocks and starts over. Then it walks the list: it replaces the value of an existing key, or appends a new node at the tail.

In Demo 3: one bin locked T1 holds bin 1 while it appends 17, and T2, which wants to append 25 to the same bin, is BLOCKED. When T1 leaves the monitor, T2 wakes up and gets it.

get() never locks

get reads the slot with a volatile read and walks the list, whose val and next fields are volatile too. It takes no lock, so in Demo 3 T3's get(9) reads bin 1 while T1 holds its lock, and returns at once. The price is that get returns the value of the most recently completed update. A put that is still in progress may or may not be visible yet. That is fine for a map: there is no moment in which a reader could see a half-built node.

Counting: baseCount and CounterCells

After an insert, addCount must add 1 to the size. A single counter that every thread CASes would be a new bottleneck. So ConcurrentHashMap counts like LongAdder: it first tries a CAS on baseCount. If that CAS fails because another thread changed baseCount in between, it adds 1 to a CounterCell picked by the thread's random probe instead. size() returns baseCount + Σ cells. In Demo 4 three inserts finish together: T1's CAS on baseCount wins, T2 and T3 go to cells, and no increment is lost. While writes are running, size() is only an estimate.

Resizing together: sizeCtl, ForwardingNode, helpTransfer

sizeCtl holds the next resize threshold (0.75 × n), here 6 for 8 bins. When addCount sees the count reach it, that thread creates nextTable with 2n bins and sets sizeCtl to a negative value that means "resizing". Bins are moved from the top down. A thread claims a stride of bins by CASing transferIndex down, so no two threads move the same bin. To move a bin, the thread locks it, splits the nodes into the lo and hi lists (the same split as in HashMap), writes them into nextTable, and leaves a ForwardingNode (hash MOVED = -1) in the old bin.

  • A put that finds a ForwardingNode calls helpTransfer: it claims the next stride and moves bins too, then repeats its put in the new table.
  • A get that finds a ForwardingNode just follows it into nextTable. Readers are never stopped by a resize.
  • The last thread to finish installs nextTable as table and sets sizeCtl to 0.75 × 2n.

Demo 5 shows this: T1's insert of the 6th entry starts the resize and claims bins 7 to 4. T2's put hits a moved bin, so T2 helps and claims bins 3 to 0. T3's get reads a moved bin through its ForwardingNode. In the JDK a stride is at least MIN_TRANSFER_STRIDE = 16 bins; the page uses 4, because with only 8 bins one thread would otherwise move everything alone.

Atomic compound operations, and no null

Each single call is thread-safe, but two calls in a row are not one atomic step. if (!map.containsKey(k)) map.put(k, v); is a race: in Demo 6 T1 and T2 both see that 5 is absent, both put, and T2's value silently replaces T1's. putIfAbsent, computeIfAbsent, compute and merge do the check and the write under the same bin lock: in the second half of the demo T2's putIfAbsent(13, …) finds T1's node and keeps it.

Null keys and values are not allowed and throw NullPointerException (Demo 7). The reason: get returning null must mean "not in the map". In a HashMap you could check containsKey afterwards, but in a concurrent map another thread could have changed the map between the two calls.

Three ways to make a map thread-safe

classlockingreaderswriters to different bins
Hashtable, Collections.synchronizedMapone lock for the whole mapwait for writers and each otherwait for each other
ConcurrentHashMap, JDK 5–716 Segments, each a small locked hash table (concurrencyLevel)no lock in the usual caserun in parallel if in different segments
ConcurrentHashMap, JDK 8+CAS for empty bins, synchronized per bin otherwisenever lockrun in parallel if in different bins

What the page leaves out

  • The table is created lazily by the first put (initTable, guarded by a CAS on sizeCtl); here it exists from the start.
  • sizeCtl during a resize is really (resizeStamp(n) << 16) + 1 + number of resizing threads; the page shows it as "negative".
  • Long bins become a TreeBin, which has its own small read/write lock so that get can still read it while it is rebalanced.
  • Contention on the cells themselves (the JDK then re-hashes the thread's probe and can double the cell array), and the real stride rule max(n / 8 / NCPU, 16).
  • Weakly consistent iterators, mappingCount(), and the parallel bulk operations (forEach, search, reduce with a parallelism threshold, run on the ForkJoinPool common pool).

See also How Java's HashMap Works, Compare-and-Swap, Mutex and Readers-Writers.