Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Concurrent hash maps

Where does a concurrent hash map spend its complexity, and why does a reader that writes not scale?

A is a hash table that many threads read and write at the same time. Its design history is best read as a derivation.

  1. One global lock. The serial fraction (α in the ) is 1, so is flat whatever the number of cores.
  2. Lock striping. Divide the table into S stripes, each with its own . The serial fraction falls by the stripe count S. Java 7's ConcurrentHashMap used 16 segments. But re-concentrates the moment key access is skewed (a few hot keys all fall in one stripe). That is the arriving on schedule.
  3. Per-bucket CAS, with a lock only on collision chains. (Java 8.) The granularity drops to a single bin.
  4. Fully lock-free designs. They remove locks entirely and pay in the one operation that is genuinely hard.

Resize is where the complexity goes

Lookup parallelizes trivially: readers just read. Insert needs one . But resize must atomically change the key-to-bucket mapping for the entire table while other operations are in flight. Every design spends its complexity budget here.

  • Java 8's ConcurrentHashMap migrates bins a few at a time, with helper threads. It leaves a ForwardingNode in each migrated bin, so a reader arriving there is sent to the new table.
  • Split-ordered lists (Shalev and Shavit) are more elegant. All items stay in one list, kept in a special recursively split order, so that doubling the bucket array adds pointers and moves no data at all.

This is the third time we meet one powerful idea:

  • Extendible hashing uses a doubling directory over buckets that do not move.
  • lets a joining node claim 1/n of the key space instead of remapping everything.
  • use a recursive ordering.

These are three designs at three scales (bucket, node, list) solving the same problem. That is the sign of a real constraint.

A reader that writes does not scale

This principle is counterintuitive enough to state twice: a reader that writes anything does not scale. A lock, a reference count, a : each one is a write to shared memory, so each creates a coherence transaction.

The consequence people often get wrong: a reader-writer lock is often worse than a plain mutex for read-heavy workloads. To take the read lock, a reader increments a shared counter. Every reader therefore invalidates every other reader's copy of that . Read throughput can decrease as you add cores.

The fixes all make readers silent (they write nothing shared):

  • per-core reader counters,
  • seqlocks (a version number the writer bumps; readers check it before and after reading and retry if it changed),
  • RCU (read-copy-update),
  • immutable snapshots.

This leads to the stated earlier.