AlgoInsight

Free lesson · Concurrency Interview Mastery

Designing a Concurrent HashMap

Hard10 min readconcurrencymultithreadinginterview-prep

A concurrent hash map is the workhorse of multithreaded programming - a key-value store that many threads read and write simultaneously without corruption and without serializing on a single lock. It's the most important concurrent data structure to understand deeply, because its design embodies the central lesson of this module: fine-grained locking and lock-free reads beat a single global lock. The naive approach - wrap a HashMap in one synchronized lock - is correct but throttles all concurrency to one operation at a time. The real designs (Java's ConcurrentHashMap being the canonical reference) achieve high throughput through lock striping (many independent locks), per-bin locking (locking only the bucket being touched), CAS for uncontended insertions, and lock-free reads (gets never block). We'll trace the evolution from global lock to the modern per-bin design, and see how reads proceed without any lock at all.

Requirements and API

A thread-safe map supporting the standard operations under heavy concurrency:

interface ConcurrentMap<K, V>:
    get(key: K) -> V or null
    put(key: K, value: V) -> V                 # returns previous value
    remove(key: K) -> V
    putIfAbsent(key: K, value: V) -> V         # atomic insert-if-absent
    # computeIfAbsent, compute, merge - atomic per-key read-modify-write

The requirements:

The design challenge is achieving thread-safety without a single global lock that would make it a glorified synchronized map.

The evolution: global lock → striping → per-bin + lock-free reads

Approach 1 - one global lock (the baseline). Wrap every operation in a single lock (Collections.synchronizedMap). Correct, but every get and put - even on unrelated keys - serializes through one lock. Zero parallelism; throughput is flat regardless of cores. This is the thing to beat.

Approach 2 - lock striping (segments). Divide the map into N independent segments, each a small hash table with its own lock. A key is routed to a segment by its hash (segment = hash % N). Operations on keys in different segments use different locks, so they proceed concurrently - concurrency level ≈ N. This was Java 7's ConcurrentHashMap (16 segments by default). Striping turns one contended lock into N less-contended locks, a huge improvement for moderate N, though concurrency is capped at N.

Approach 3 - per-bin locking + CAS + lock-free reads (the modern design). Java 8's ConcurrentHashMap went finer-grained: instead of N segment locks, it locks at the granularity of individual bins (buckets). The map is an array of bins; each bin holds a linked list of nodes (or a balanced tree if the bin grows large). The operations:

table = array of bins (each bin = head of a node list, or a tree)

function get(key):                       # NO LOCK
    h = hash(key)
    bin = table[h & (table.length - 1)]   # volatile read of the bin head
    for node in bin:                      # traverse without locking
        if node.key == key: return node.value
    return null

function put(key, value):
    h = hash(key)
    while true:
        i = h & (table.length - 1)
        if table[i] == null:              # EMPTY bin -> CAS a new node in (lock-free)
            if casBin(table, i, null, new Node(key, value)): return null
            # CAS failed (someone else inserted) -> retry the loop
        else:
            synchronized (table[i]):      # lock ONLY this bin's head node
                # traverse the bin; update existing key or append new node
                ...
            return ...

Three ideas make this fast. Lock-free reads: get takes no lock - it does a volatile read of the bin head and traverses the (immutably-linked or carefully-published) node list. Because node fields are final/volatile and insertions publish nodes safely, a reader always sees a consistent value without blocking. Reads scale perfectly with cores. CAS for empty bins: inserting into an empty bin is done with a single compareAndSet (no lock) - the common case of adding a new key to an unused bucket is lock-free. Per-bin locking for collisions: only when a bin is non-empty (a hash collision) does put lock - and it locks only that one bin's head node (synchronized on the head), so writes to different bins never contend. Contention is confined to concurrent writes hashing to the same bin (rare with a good hash and adequate table size).

flowchart TD
    GET["get(key) - NO LOCK"] --> GH["bin = table[hash & mask]<br/>(volatile read)"]
    GH --> GTRAV["traverse bin list (no lock)"] --> GRET["return value / null"]
    PUT["put(key, value)"] --> PH["i = hash & mask"]
    PH --> EMPTY{"table[i] empty?"}
    EMPTY -->|yes| CAS["CAS new node into table[i]<br/>(LOCK-FREE); retry if CAS fails"]
    EMPTY -->|no| LOCK["synchronized(table[i])<br/>lock ONLY this bin"]
    LOCK --> INS["traverse + update/append"]
    note["Lock-free READS (volatile). CAS for EMPTY bins. Per-BIN lock for collisions.<br/>Different bins never contend; reads never block. (Java 8 ConcurrentHashMap.)"]

This flowchart shows a modern concurrent hash map, modeled on Java 8's ConcurrentHashMap. The map is an array of bins, each holding a list of nodes. A get operation takes no lock at all: it does a volatile read of the bin head and traverses the list, always seeing a consistent value because nodes are safely published. This lets reads scale perfectly with cores. A put operation computes the bin index. If the bin is empty, it inserts a new node with a single atomic compare-and-set - lock-free for the common case of adding a key to an unused bucket - retrying if the compare-and-set fails because another thread got there first. If the bin is non-empty, meaning a hash collision, it synchronizes on just that one bin's head node and traverses the list to update an existing key or append a new node. Because it locks only the individual bin, writes to different bins never contend, and reads never block at all.

Why lock-free reads and per-bin locking matter

The two design choices that make a concurrent hash map scale are lock-free reads and per-bin write locking. Reads are typically the dominant operation, and making them lock-free - relying on memory-visibility guarantees (volatile bin heads, safely-published immutable nodes) rather than locks - means readers never block and never contend, so read throughput scales linearly with cores. This depends on the memory model (Module 5/6): the bin-head array slots are volatile, and a node's key/hash are final (immutable, safely published by the constructor), so a reader either sees a fully-constructed node or doesn't see it at all - never a half-built one. Per-bin write locking confines write contention to the specific bin being modified: two puts to different keys that hash to different bins proceed fully in parallel; only puts colliding in the same bin serialize, and with a good hash function and load factor, collisions are rare. This is the lock-striping idea taken to its finest granularity - one "stripe" per bin. The combination means the map's throughput is bounded not by a global lock but by actual contention on individual keys, which in real workloads is low. Understanding why reads need no lock (memory model guarantees) and why writes lock per-bin (confine contention) is the heart of the design.

Important: A concurrent hash map must beat the single global lock (synchronized map), which serializes everything. The evolution: lock striping (Java 7 - N segments each with its own lock; concurrency ≈ N) → per-bin locking + CAS + lock-free reads (Java 8 - the modern design). In the modern design: the map is an array of bins (lists, treeified when large); get takes NO lock (volatile read of the bin head + traverse - relies on the memory model: volatile slots, final/safely-published nodes, so readers never see a half-built node); put into an empty bin uses CAS (lock-free common case); put into a non-empty bin locks only that bin's head (synchronized), so different bins never contend. Atomic compound ops (putIfAbsent, computeIfAbsent) avoid the check-then-act race. Size uses a striped counter (LongAdder-style cells), not one contended counter. Lock-free reads (memory-model-backed) and per-bin write locking (confined contention) are the standout points.

Trade-offs and the hard parts

A thorough answer addresses several subtleties. Atomic compound operations: putIfAbsent must atomically check-and-insert - a naive if (!map.contains(k)) map.put(k,v) has the check-then-act race; the map provides putIfAbsent/computeIfAbsent that do it atomically under the bin lock. Resizing: growing the table while other threads read/write is genuinely hard - Java 8's map does cooperative resizing, where multiple threads help transfer bins to the new table, and readers/writers check whether a bin is being moved (a "forwarding node" marks transferred bins). Size counting: a single size counter would be a contention hotspot (every put/remove updates it), so the map uses a striped counter - an array of counter cells (like LongAdder) that threads update independently, summed on demand - trading exact-instant accuracy for scalability. Treeification: if many keys collide in one bin (bad hash or attack), the bin's linked list degrades to O(n) lookup; Java 8 converts a bin to a balanced tree (red-black) past a threshold (8 nodes), restoring O(log n). The design lesson: per-bin locking + lock-free reads is the core; resizing, striped size counting, and treeification are the genuinely hard refinements that production maps handle - worth naming to show depth, while noting you'd use the library rather than hand-roll them.

The memory model: why lock-free reads are safe

The claim that reads need no lock deserves careful justification, because it's where the subtlety lives. A reader traverses a bin's node list without any lock - so how is it guaranteed to see correct data while writers are concurrently inserting? The answer is the memory model (Module 5), and it rests on three guarantees. First, the bin-head array slots are volatile: when a writer CAS-es or assigns a new head node, the write is published with release semantics, and a reader's volatile read of the slot has acquire semantics - so a reader that sees the new head also sees everything the writer did before publishing it (a happens-before edge). Second, node fields are final or volatile: a node's key and hash are final, set in the constructor; the Java memory model guarantees that once a final field is safely published (the node reference becomes visible), the final fields are fully visible too - so a reader never sees a node with a published reference but an uninitialized key. The value and next are volatile, so updates to them are visible. Third, insertions don't mutate existing nodes destructively in a way readers can observe torn: appending links a new node at the end (a single volatile write to next), and updating a value is a single volatile write - both atomic with respect to a reader. Together these mean a reader sees a consistent snapshot: either the old state or the new state of any single field, never a half-written one. This is why the design can skip read locks - not because locking is "optional," but because the memory model provides exactly the visibility and atomicity guarantees that a lock would otherwise enforce. Lock-free reads are a memory-model achievement, not a shortcut, and articulating this is what separates a deep answer from a hand-wave.

Note: The concurrent hash map embodies the single most important principle of high-performance concurrent data structures: make the common, dominant operation lock-free or contention-free, and confine locking to the rare cases. For a hash map, reads dominate and uncontended writes (to distinct bins) are common, so the design makes reads lock-free (memory model) and uncontended inserts lock-free (CAS into empty bins), locking only for the genuinely contended case of a write colliding with another write in the same bin. This "optimize the common case, pay the cost only on real contention" philosophy is what every scalable concurrent structure does, and it's the opposite of the naive "lock everything" instinct. You see the same philosophy in the two-lock blocking queue (separate the contended ends), in lock-free queues (CAS the common path, retry only on contention), in read-copy-update (RCU, where reads are entirely free and only writers coordinate), and in striped counters (each thread updates its own cell, contention only on the rare sum). The transferable design instinct: when building a concurrent structure, ask "what's the dominant operation, and can I make it free of locks and contention, pushing the synchronization cost onto the rarer operations?" A global lock fails precisely because it taxes the common case (every read) with the cost needed only for the rare case (conflicting writes). Recognizing and inverting that - cheap common path, expensive rare path - is the core craft of concurrent data-structure design, and the concurrent hash map is its clearest teaching example.

The interview angle

Interview: "Design a concurrent hash map" is a top concurrent-data-structure question. The expected arc: reject the single global lock, then describe lock striping (segments) and the modern per-bin locking + CAS + lock-free reads. Distinguishing points: (1) lock-free reads and why they're safe (memory model - volatile bin heads, final/safely-published nodes, so no half-built node is seen) - the deepest insight; (2) CAS for empty-bin insertion (lock-free common case) and per-bin locking for collisions (confined contention); (3) atomic compound operations (putIfAbsent/computeIfAbsent) to avoid the check-then-act race; (4) the hard refinements - cooperative resizing, striped size counter (LongAdder, avoid a contended counter), treeification of long bins; (5) striping concurrency level vs. per-bin granularity. Follow-ups push on resizing and size counting. Lock-free reads (with the memory-model justification) and per-bin locking are the standout signals.

Quick reference

The workhorse concurrent data structure - its design teaching the module's core lesson that fine-grained locking and lock-free reads beat a single global lock:

CONCURRENT HASHMAP: thread-safe get/put/remove; high concurrency; beat the GLOBAL LOCK

EVOLUTION:
  1. GLOBAL LOCK (synchronized map): correct but serializes everything -> no parallelism
  2. LOCK STRIPING (Java 7): N segments, each its own lock; concurrency ~= N
  3. PER-BIN + CAS + LOCK-FREE READS (Java 8): finest granularity

MODERN DESIGN (array of bins; lists, treeified when large):
  get(k): NO LOCK -- volatile read of bin head + traverse
          (safe via memory model: volatile slots + final/safely-published nodes)
  put(k,v): empty bin -> CAS new node in (LOCK-FREE common case; retry on CAS fail)
            non-empty bin -> synchronized(bin head) -- lock ONLY this bin -> traverse/insert
  -> different bins never contend; reads never block

KEY POINTS:
  - LOCK-FREE READS: rely on memory model (volatile + final), not locks -> scale with cores
  - CAS for empty bins; PER-BIN lock for collisions (confined contention)
  - ATOMIC compound ops (putIfAbsent/computeIfAbsent) -> no check-then-act race
  - SIZE: striped counter (LongAdder cells), NOT one contended counter

HARD REFINEMENTS: cooperative RESIZING (forwarding nodes, threads help transfer);
  TREEIFICATION (bin list -> red-black tree past 8 nodes -> O(log n))

The concurrent hash map established lock-free reads and per-bin locking. The next structure is the blocking queue - the producer-consumer buffer as a reusable data structure - where the focus shifts to condition-variable coordination and the two-lock trick for concurrent enqueue/dequeue.

Back to Concurrency Interview Mastery