Free lesson · Concurrency Interview Mastery

Exercise: Design a Concurrent HashMap

Hard6 min readconcurrencymultithreadinginterview-prep

This exercise builds lock striping, refines to per-bin locking with lock-free reads, and diagnoses the global-lock and check-then-act bugs. Reason each through before the solution - the goal is to see how finer-grained locking and lock-free reads beat a single global lock, and why reads can safely skip locking.

Important: Two anchors: operations on different keys should not contend (stripe the locks - by segment, then by bin), and reads need no lock if the structure relies on the memory model (volatile bin heads, safely-published immutable nodes) so a reader never sees a half-built node.

Part 1 - Lock striping

Your task: Implement a striped concurrent map: N segments, each a small table with its own lock; route keys to segments by hash. Why does this beat a global lock?

segments = array of N segments, each { table, lock }. segmentFor(key) = segments[hash(key) & (N-1)]. get/put/remove: seg = segmentFor(key); seg.lock.lock(); try { ... } finally { seg.lock.unlock() }. Operations on keys in different segments use different locks → concurrency up to N. A global lock serializes all operations; striping serializes only those hitting the same segment. </details>

Part 2 - Per-bin locking with lock-free reads

Your task: Refine to per-bin locking: CAS for empty bins, lock only the bin head for collisions, and lock-free reads. Why can get skip locking?

Bins array; get(k): volatile read of table[i], traverse list, no lock. put(k,v): if table[i] empty, CAS(table, i, null, newNode); else synchronized(table[i]) { traverse + insert/update }. Reads skip locking because the bin-head slots are volatile and nodes are safely published (final key/hash) - a reader sees either a fully-constructed node or none, never a torn one. Per-bin locking means different bins never contend. </details>

Part 3 - Find the bugs

// Bug A - global lock:
function get(key):  synchronized(this) { return table.get(key) }   // <-- all reads serialize
function put(k,v):  synchronized(this) { return table.put(k, v) }

// Bug B - non-atomic putIfAbsent:
function putIfAbsent(key, value):
    if not map.containsKey(key):          // <-- check
        map.put(key, value)               // <-- act (separate)
        return null
    return map.get(key)

Your task: Identify the scalability problem in A and the concurrency bug in B.

Bug A: a single lock on this serializes every operation - even reads on unrelated keys - so throughput is flat regardless of cores (no parallelism). It's correct but defeats the purpose; stripe the locks or lock per-bin, and make reads lock-free. Bug B: containsKey then put are separate - two threads can both find the key absent and both put, the second overwriting the first (lost insert, or both think they inserted). Fix: an atomic putIfAbsent performed under the bin lock (or via CAS), so the check-and-insert is one indivisible operation. </details>

Solution

Part 1 - Lock striping

class Segment: table = HashMap(); lock = ReentrantLock()

segments = array of N Segments        # N a power of 2 (e.g., 16)

function segmentFor(key):
    return segments[hash(key) & (N - 1)]

function get(key):
    seg = segmentFor(key)
    seg.lock.lock()
    try: return seg.table.get(key)
    finally: seg.lock.unlock()

function put(key, value):
    seg = segmentFor(key)
    seg.lock.lock()
    try: return seg.table.put(key, value)
    finally: seg.lock.unlock()

The map is split into N segments, each an independent small hash table with its own lock. A key is routed to a segment by its hash, so operations on keys in different segments acquire different locks and run concurrently - concurrency up to N. This beats a global lock because a global lock forces all operations to serialize through one lock (one operation at a time, no matter how many cores or how unrelated the keys); striping confines contention to operations hitting the same segment, which with N segments is roughly 1/N of the contention. This is Java 7's ConcurrentHashMap design. (Part 2 goes finer.)

Part 2 - Per-bin locking with lock-free reads

table = volatile array of bins        # each bin = head Node (list), or null

function get(key):                    # NO LOCK
    h = hash(key); i = h & (table.length - 1)
    node = table[i]                   # volatile read of bin head
    while node != null:
        if node.hash == h and node.key == key: return node.value
        node = node.next
    return null

function put(key, value):
    h = hash(key)
    while true:
        i = h & (table.length - 1)
        if table[i] == null:
            if CAS(table, i, null, new Node(h, key, value, null)):  # lock-free empty-bin insert
                return null
            # CAS failed -> someone inserted -> retry
        else:
            synchronized (table[i]):                                 # lock ONLY this bin
                node = table[i]
                while true:
                    if node.hash == h and node.key == key:
                        old = node.value; node.value = value; return old
                    if node.next == null: node.next = new Node(h, key, value, null); return null
                    node = node.next

Reads take no lock: a volatile read of the bin head followed by list traversal. This is safe because the bin-head array is volatile (a reader sees the latest published head) and nodes are safely published - their hash and key are final, set in the constructor before the node is CAS'd or linked in, so a reader sees a fully-formed node or none at all, never a half-built one. Writes use CAS for the empty-bin case (lock-free) and synchronized on the bin head only for collisions, so writes to different bins never contend. This is the finest granularity - one lock stripe per bin - plus lock-free reads, matching Java 8's ConcurrentHashMap.

Part 3 - The bugs

Bug A - global lock kills concurrency. Locking synchronized(this) for every get and put means a single lock guards the entire map, so all operations serialize - even two reads of completely unrelated keys can't proceed in parallel. Throughput is flat: adding cores doesn't help, because only one thread is ever inside the map. It's correct (no corruption) but defeats the entire purpose of a concurrent map. The fix is finer-grained locking: stripe the locks across segments (Part 1) or lock per-bin (Part 2), and make reads lock-free. A concurrent map's whole value is letting unrelated operations run in parallel, which a global lock forbids.

Bug B - non-atomic putIfAbsent (check-then-act). containsKey(key) and put(key, value) are two separate operations. Two threads calling putIfAbsent for the same absent key can both execute containsKey (both get false), then both put - the second overwrites the first's value, and both believe they inserted (or one's insert is silently lost). This violates the atomic insert-if-absent contract. The fix is to make the check-and-insert atomic: perform it under the bin's lock (traverse the bin and insert only if the key isn't found, all while holding the bin lock), or use a CAS-based insert. This is the check-then-act race (Module 6) again - the reason concurrent maps provide atomic compound operations (putIfAbsent, computeIfAbsent) rather than leaving callers to compose non-atomic primitives.

Both bugs reinforce the design: fine-grained (not global) locking for concurrency (Bug A), and atomic compound operations for race-free per-key updates (Bug B).

Common mistakes

Warning: Watch for: (1) A single global lock - serializes everything; stripe or lock per-bin. (2) Non-atomic putIfAbsent - check-then-act race; use an atomic compound operation under the bin lock or via CAS. (3) Locking reads - unnecessary if the structure uses volatile heads + safely-published nodes; lock-free reads scale far better. (4) Non-volatile bin heads - readers may see stale heads or half-built nodes; the bin array must be volatile and nodes safely published. (5) A single contended size counter - hotspot; use a striped counter (LongAdder). (6) Ignoring long-bin degradation - a bad hash makes a bin O(n); treeify past a threshold.

Why this exercise matters for interviews

Interview: The concurrent hash map is a top interview data structure, and this exercise mirrors the expected progression. Part 1 (lock striping) shows you understand confining contention. Part 2 (per-bin + lock-free reads) is the modern design - CAS for empty bins, per-bin locking for collisions, and lock-free reads justified by the memory model (volatile heads, safely-published nodes). Part 3 (bugs) targets the two signature errors: the global-lock anti-pattern (no concurrency) and non-atomic putIfAbsent (check-then-act). The throughline interviewers reward: beat the global lock with striping then per-bin locking, make reads lock-free and explain why it's safe, provide atomic compound operations, and know the hard refinements (resizing, striped size counter, treeification). Lock-free reads with the memory-model justification are what most distinguish a strong answer.

Back to Concurrency Interview Mastery