Concurrent Hash Map — Interview Preparation¶

Tiered Q&A (Junior → Middle → Senior → Professional), 50 questions with model-answer focus, plus a rapid-fire round, red-flag guide, and two full coding challenges — a sharded / striped concurrent map and a lock-free counter variant — in Go, Java, and Python.

Cross-links: hash tables, CAS, RCU.

How to use this page: answer out loud, then check against the model focus. For the coding challenge, implement all three languages and run the Go version with -race. The interviewer cares most about whether your compound operations are atomic and whether you can articulate the read:write-ratio trade-off.

Table of Contents¶

1. Junior Questions
2. Middle Questions
3. Senior Questions
4. Professional Questions
5. Rapid-Fire Round
6. Coding Challenge — Sharded Concurrent Map

Junior Questions¶

Focus: definitions, why plain maps break, the coarse-lock fix, and the built-in concurrent map per language. If you can explain Q2 and Q8 clearly, you're past the junior bar.

Deeper sample answers

Q2 — Why unsafe? "A put computes a bucket, walks/edits a chain, increments size, and may trigger a resize that reallocates the whole table. None of that is atomic. If two goroutines run it interleaved, one can overwrite the other's next pointer (dropping entries or creating a cycle that makes reads spin forever), or both read size=10 and write 11 (a lost update). Go's runtime actively detects concurrent map writes and crashes the program to stop the corruption."

Q1 — What is it? "A hash map that's safe for simultaneous use by many threads or goroutines. It keeps the same average O(1) get/put/delete, but its operations are designed so that concurrent calls don't corrupt the buckets, the size counter, or an in-progress resize. Every major language ships one: Go's sync.Map (or a sharded map), Java's ConcurrentHashMap, and in Python a dict whose single operations are atomic under the GIL but whose compound operations need a Lock."

Q8 — check-then-act: "has and put are each individually safe, but the window between them is not. Thread A checks (absent), thread B inserts k, thread A inserts k — overwriting B. The fix is a single atomic operation that does the check and the insert under one lock: LoadOrStore (Go), putIfAbsent (Java)."

Q6 — m[k]++: "It expands to: read the current value, add one, write it back. Two threads can both read the same old value before either writes, so one increment is lost. Worse, in Go it's also a data race on the map's internals, which the runtime may turn into a crash. The fix is to make the whole read-add-write happen under one lock, or use a built-in atomic like Java's merge(k, 1, Integer::sum)."

Q10 — Big-O unchanged: "Each operation is still average O(1) — the hash, bucket lookup, and chain step don't get asymptotically slower because of threads. What concurrency affects is throughput: ops per second across all threads. A single global lock keeps O(1) per op but serializes everything, so adding cores buys nothing. Finer-grained designs keep O(1) per op and let throughput scale with cores."

Middle Questions¶

Deeper sample answers

Q16 — Java 8 design: "Java 8 dropped segments. The table is one flat array. On put: if the bucket is empty, a single CAS installs the node — completely lock-free, retried on failure. If occupied, synchronized on the bucket's first node, then walk the chain or tree. So contention is per-bucket (thousands of locks) instead of per-segment (16). get stays lock-free via volatile reads. Long chains treeify to red-black trees for O(log n) worst case."

Q20 — size problem: "You can partition buckets perfectly and still funnel every insert through one size++, making it the single hottest cache line — worse than any bucket. The fix is a striped counter: each thread CASes its own padded cell; size() sums them. The trade-off is that the count is now approximate/weakly-consistent, which is fine."

Q13 — why one lock fails: "Amdahl's Law: if every operation must pass through one serial gate, the serial fraction is essentially 100%, so adding cores gives no speedup. Concretely, threads queue on the lock, the OS parks them (microsecond context switches that dwarf the O(1) map work), and the lock word plus the size field bounce between core caches. Throughput flattens at about one effective thread. Partition the lock — striping, sharding, or per-bucket CAS — and disjoint keys stop contending."

Q22 — CHM vs synchronizedMap: "synchronizedMap wraps a HashMap so every method takes one shared lock — all reads and writes serialize, and you must manually hold that lock for the entire duration of any iteration or you get a ConcurrentModificationException. ConcurrentHashMap locks per bucket, so reads are lock-free and writes to different buckets run in parallel; its iterator is weakly consistent (never throws); it offers atomic compound ops like merge and computeIfAbsent; and it forbids null keys/values. Use CHM unless you specifically need nulls and have negligible contention."

Senior Questions¶

Deeper sample answers

Q31 — concurrent resize: "A stop-the-world rehash pauses for O(n) — fatal for tail latency. Production maps move incrementally: Java 8 CHM doubles the table and transfers buckets in stride-sized chunks, conscripting any thread that touches the map during resize to help move a chunk first. Each moved bucket's old slot becomes a ForwardingNode pointing to the new table, so concurrent reads/writes are redirected and never miss a transferred key. Redis keeps two hash tables and migrates a few buckets per command, checking both during the migration."

Q27/28 — split-ordered list: "Shalev and Shavit's lock-free hash map keeps all keys in a single lock-free sorted linked list, ordered by the bit-reversed hash. The bucket array is just an array of shortcut pointers into that list. Resizing doesn't move any data — it only adds more bucket pointers that subdivide existing buckets. Bit-reversal is the trick: when the table doubles, each bucket splits in two, and bit-reversed ordering guarantees the split point already exists as a position in the list, so the new bucket pointer inserts in O(1). The catch is safe memory reclamation — hazard pointers or epochs — since there's no GC in the original C setting."

Q33 — false sharing: "Two unrelated hot fields that happen to share a 64-byte cache line cause that line to ping-pong between cores even though the threads touch different fields. For a concurrent map this kills striping: if all your stripe locks or counter cells sit in one array packed together, they share lines and striping gains nothing. The fix is padding each hot field to its own cache line — Java's @Contended, or manual padding fields in Go. LongAdder's cells are @Contended for exactly this reason."

Professional Questions¶

Focus: prove, don't assert. Linearization points, happens-before, invariants, progress classes, and impossibility results. Expect to defend a design against a skeptical reviewer.

Deeper sample answers

Q40 — lock-freedom proof: "Lock-freedom requires that in any infinite execution, infinitely many operations complete. In the split-ordered list, an operation either succeeds its CAS (and finishes) or fails. A CAS on pred.next fails only because another thread's CAS on the same word succeeded since this thread last read it. So every failed CAS is paired with a successful one by another thread — a completed unit of progress. The system therefore cannot have all threads loop forever with none completing; some thread always advances. That's lock-free. It's not wait-free because one unlucky thread might lose every race and retry without bound."

Q42 — exact size: "An exact, linearizable size must equal (#insert − #delete) linearization points before some instant τ. If size() reads shard/cell counts without blocking mutators, two inserts can linearize between the reads of two shards, so the returned sum corresponds to no single τ — that violates linearizability. To be exact you must take a consistent cut, i.e. a barrier over every shard, which is global serialization. Hence production maps deliberately return an approximate striped sum."

Q43 — RCU read cost: "An RWMutex reader increments a shared reader-count — a single atomic write to one cache line that every reader touches, so that line bounces between cores and caps read throughput at roughly one-over-coherence-latency. An RCU reader does no shared write at all; on a non-preemptible kernel build rcu_read_lock compiles to nothing. With no shared store there's no coherence invalidation from reads, so reads scale linearly with cores — roughly cores-over-traversal-time. The speedup over an RWMutex on the read side is about cores times the ratio of coherence latency to traversal time, which is large for small structures with many cores. The cost moves to writers, who pay a grace period, and to memory, which holds stale versions until reclamation."

Q44 — memory model: "The writer fully builds the node, then publishes it with a release store (a volatile write or a CAS). A reader that observes the published pointer via an acquire load is guaranteed to see every write the writer made before the release — so it never sees a half-constructed node with a garbage next. Without this release/acquire pairing, the CPU or compiler may reorder the field writes after the pointer write, and a lock-free reader observes a torn node. This is why CHM marks node fields volatile; on weakly ordered hardware like ARM it's a correctness requirement, not an optimization."

Q45 — no hazard pointers on JVM: "Safe memory reclamation means never freeing a node while a reader still holds a pointer to it. In C/C++/Rust a lock-free map must track that explicitly with hazard pointers (each thread publishes the pointers it's about to dereference; a node is freed only if no hazard slot references it) or epoch-based reclamation. On the JVM and in Go, the garbage collector already guarantees a node is collected only when unreachable — which is exactly the SMR safety condition — so those maps need no hazard pointers. The cost moves into GC pressure instead."

Q41 — resize invariants: "Three. Single-mover: a claiming CAS on the bucket's state means at most one thread transfers a given bucket, so no torn or double transfer. Redirect: once a bucket's old slot holds a ForwardingNode, every op on a key hashing there follows the forward into the new table. Key-conservation: at every instant each key is findable in exactly one place — in the old table if its bucket is unmoved, in the new table (via the forward) if moved. Together these guarantee no read misses a present key and no write lands in an abandoned bucket."

Mixed Scenario Questions¶

Deeper sample answers

Q46 — the cache anti-pattern: "Two bugs in one line. First, check-then-act: between get returning null and put, another thread can insert k, and this thread overwrites it. Second, the thundering herd: under a cold cache, dozens of threads all see null for the same hot key and all run the expensive load, hammering the backend. computeIfAbsent(k, this::load) fixes both — it's atomic per key and runs the loader at most once. Caveat: the loader holds the bin lock, so for a slow loader prefer loading outside and putIfAbsent, or a cache library like Caffeine that coalesces loads without holding bin locks."

Q48 — ARM vs x86: "x86 has Total Store Order — it won't reorder a store ahead of an earlier store, which accidentally preserves the 'build node, then publish pointer' ordering even if you forgot the barrier. ARM and POWER are weakly ordered: the publish store can become visible before the node's field writes, so a lock-free reader on ARM can observe the pointer but stale/garbage fields. The bug was always present; x86 just hid it. The fix is explicit release/acquire (or volatile in Java, sync/atomic in Go), which the built-in concurrent maps already use."

Rapid-Fire Round¶

• Q: Most-contended cache line in a naive concurrent map? A: The single size counter.
• Q: CHM treeify threshold? A: Chain > 8 and table ≥ 64.
• Q: Go's read-optimized built-in concurrent map? A: sync.Map.
• Q: Atomic get-or-insert in Go? A: LoadOrStore.
• Q: Atomic load-through in Java? A: computeIfAbsent.
• Q: Does the GIL make d[k] += 1 atomic? A: No (read-modify-write).
• Q: Reclamation scheme used by the Linux kernel hash table? A: RCU.
• Q: One-word reason RWMutex reads don't scale infinitely? A: Shared reader-count cache line.
• Q: Strongest read progress guarantee, achievable by COW/RCU? A: Wait-free.
• Q: What redirects ops during CHM resize? A: ForwardingNode.
• Q: ABA problem in one line? A: CAS sees value equality, not identity — a freed+reused address fools it.
• Q: Why no hazard pointers needed on the JVM? A: GC frees only unreachable nodes, satisfying the safety condition.
• Q: Linearization point of a lock-free insert? A: The successful CAS that installs the node.
• Q: Fail-fast vs weakly consistent iterator? A: Fail-fast throws CME; weakly consistent never throws and sees a moving target.
• Q: Power-of-two shard count lets you replace % with what? A: hash & (N-1).
• Q: One reason RWMutex reads still don't scale perfectly? A: Reader-count is a shared write → bouncing cache line.
• Q: CAS's consensus number, and why it matters? A: ∞ — it can coordinate any number of threads, which atomic registers (consensus number 1) cannot, so lock-free contested inserts require it.
• Q: What does @Contended (Java) do? A: Pads a field to its own cache line to prevent false sharing.
• Q: Why does Go's sync.Map excel at stable keys? A: Stable keys live in its lock-free read map; churny writes force locking the dirty map and promotions.
• Q: Treeify untreeify thresholds? A: Treeify at chain > 8 (table ≥ 64); untreeify at ≤ 6.

Red Flags Interviewers Watch For¶

These are the answers that quietly fail a concurrency interview:

The meta-signal interviewers want: you reason about operation-level atomicity, the read:write ratio, and the cost model, not just "is there a lock somewhere."

Complexity Quick Reference¶

Memorize this table — the "sync cost" column is what distinguishes a candidate who understands concurrent maps from one who only knows plain hash-map Big-O.

One-liner to anchor the whole topic: "Concurrency doesn't change a hash map's Big-O; it changes its throughput, and the entire design space is about partitioning the lock (striping, sharding, per-bucket CAS) so disjoint keys never contend — while making reads pay as close to nothing as possible (lock-free, RCU, or COW) for read-mostly workloads."

Coding Challenge — Sharded Concurrent Map¶

Problem. Implement a thread-safe sharded (lock-striped) concurrent map ConcurrentCounter with these operations, all safe under heavy concurrency: - Inc(key) — atomically increment the counter for key. - Get(key) — return the current count (0 if absent). - Total() — return the sum of all counters (a best-effort snapshot is acceptable).

Requirements. Use N = 32 shards, each a (lock, map) pair, routing keys by hash. Inc must be a correct atomic read-modify-write within its shard. Disjoint-shard operations must run in parallel. Demonstrate with many threads each incrementing and assert the total equals the number of increments.

Go¶

package main

import (
    "fmt"
    "hash/fnv"
    "sync"
)

const shards = 32 // power of two

type bucket struct {
    mu sync.Mutex
    m  map[string]int64
}

type ConcurrentCounter struct {
    b [shards]*bucket
}

func New() *ConcurrentCounter {
    c := &ConcurrentCounter{}
    for i := range c.b {
        c.b[i] = &bucket{m: make(map[string]int64)}
    }
    return c
}

func (c *ConcurrentCounter) shard(key string) *bucket {
    h := fnv.New32a()
    h.Write([]byte(key))
    return c.b[h.Sum32()&(shards-1)] // hash & (N-1)
}

func (c *ConcurrentCounter) Inc(key string) {
    b := c.shard(key)
    b.mu.Lock()
    b.m[key]++ // atomic RMW within the shard lock
    b.mu.Unlock()
}

func (c *ConcurrentCounter) Get(key string) int64 {
    b := c.shard(key)
    b.mu.Lock()
    defer b.mu.Unlock()
    return b.m[key]
}

func (c *ConcurrentCounter) Total() int64 {
    var total int64
    for _, b := range c.b { // best-effort snapshot across shards
        b.mu.Lock()
        for _, v := range b.m {
            total += v
        }
        b.mu.Unlock()
    }
    return total
}

func main() {
    c := New()
    const threads, per = 16, 10000
    var wg sync.WaitGroup
    for t := 0; t < threads; t++ {
        wg.Add(1)
        go func(t int) {
            defer wg.Done()
            for i := 0; i < per; i++ {
                c.Inc(fmt.Sprintf("k-%d", i%100)) // 100 distinct keys
            }
        }(t)
    }
    wg.Wait()
    fmt.Println("total =", c.Total()) // 16 * 10000 = 160000
}

Java¶

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class ConcurrentCounter {
    private static final int SHARDS = 32; // power of two
    private final Object[] locks = new Object[SHARDS];
    @SuppressWarnings("unchecked")
    private final Map<String, Long>[] maps = new HashMap[SHARDS];

    public ConcurrentCounter() {
        for (int i = 0; i < SHARDS; i++) {
            locks[i] = new Object();
            maps[i] = new HashMap<>();
        }
    }

    private int idx(String key) {
        // spread bits; mask to power-of-two range
        int h = key.hashCode();
        h ^= (h >>> 16);
        return h & (SHARDS - 1);
    }

    public void inc(String key) {
        int i = idx(key);
        synchronized (locks[i]) {                 // per-shard lock
            maps[i].merge(key, 1L, Long::sum);    // atomic RMW within shard
        }
    }

    public long get(String key) {
        int i = idx(key);
        synchronized (locks[i]) {
            return maps[i].getOrDefault(key, 0L);
        }
    }

    public long total() {
        long sum = 0;
        for (int i = 0; i < SHARDS; i++) {
            synchronized (locks[i]) {
                for (long v : maps[i].values()) sum += v;
            }
        }
        return sum; // best-effort snapshot
    }

    public static void main(String[] args) throws InterruptedException {
        ConcurrentCounter c = new ConcurrentCounter();
        int threads = 16, per = 10_000;
        ExecutorService pool = Executors.newFixedThreadPool(threads);
        for (int t = 0; t < threads; t++) {
            pool.submit(() -> {
                for (int i = 0; i < per; i++) c.inc("k-" + (i % 100));
            });
        }
        pool.shutdown();
        pool.awaitTermination(1, TimeUnit.MINUTES);
        System.out.println("total = " + c.total()); // 160000
    }
}

Python¶

import threading

SHARDS = 32  # power of two

class ConcurrentCounter:
    def __init__(self):
        self._locks = [threading.Lock() for _ in range(SHARDS)]
        self._maps = [dict() for _ in range(SHARDS)]

    def _idx(self, key):
        return (hash(key) & 0x7FFFFFFF) & (SHARDS - 1)

    def inc(self, key):
        i = self._idx(key)
        with self._locks[i]:                       # per-shard lock
            self._maps[i][key] = self._maps[i].get(key, 0) + 1  # atomic RMW

    def get(self, key):
        i = self._idx(key)
        with self._locks[i]:
            return self._maps[i].get(key, 0)

    def total(self):
        s = 0
        for lock, m in zip(self._locks, self._maps):  # best-effort snapshot
            with lock:
                s += sum(m.values())
        return s

if __name__ == "__main__":
    c = ConcurrentCounter()
    threads, per = 16, 10_000
    def work():
        for i in range(per):
            c.inc(f"k-{i % 100}")
    ts = [threading.Thread(target=work) for _ in range(threads)]
    for t in ts: t.start()
    for t in ts: t.join()
    print("total =", c.total())  # 160000

Discussion points an interviewer will probe: - Why per-shard locks instead of one lock? Disjoint keys hit different shards → parallel Inc. - Is Total() linearizable? No — it's a best-effort snapshot; an exact count would need a global barrier (see professional Q42). - How would you make Get/Inc lock-free? Replace map+lock shards with ConcurrentHashMap + merge, or atomic CAS per cell. - What about false sharing? Pad shard structs to a cache line so adjacent shard locks don't bounce. - How would you grow it? Per-shard incremental resize at load > 0.75, consulting both tables during migration (tasks 11–12).

Follow-up: make it lock-free with the built-in concurrent map¶

Interviewers often ask for a second iteration that removes explicit locks by delegating to the language's concurrent map and its atomic counter primitive.

Go (built-in atomics + sync.Map)¶

package main

import (
    "fmt"
    "sync"
    "sync/atomic"
)

// Lock-free-ish: each key maps to a *int64 counter we bump with atomic.AddInt64.
type LFCounter struct{ m sync.Map } // key -> *int64

func (c *LFCounter) Inc(key string) {
    v, _ := c.m.LoadOrStore(key, new(int64)) // atomic get-or-insert of the cell
    atomic.AddInt64(v.(*int64), 1)            // lock-free increment
}
func (c *LFCounter) Get(key string) int64 {
    if v, ok := c.m.Load(key); ok {
        return atomic.LoadInt64(v.(*int64))
    }
    return 0
}

func main() {
    c := &LFCounter{}
    var wg sync.WaitGroup
    for t := 0; t < 16; t++ {
        wg.Add(1)
        go func() { defer wg.Done(); for i := 0; i < 10000; i++ { c.Inc("k") } }()
    }
    wg.Wait()
    fmt.Println(c.Get("k")) // 160000
}

Java (ConcurrentHashMap + LongAdder)¶

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.LongAdder;

public class LFCounter {
    private final ConcurrentHashMap<String, LongAdder> m = new ConcurrentHashMap<>();
    public void inc(String key) {
        m.computeIfAbsent(key, k -> new LongAdder()).increment(); // striped, lock-free
    }
    public long get(String key) {
        LongAdder a = m.get(key);
        return a == null ? 0 : a.sum();
    }
}

Python (note: GIL serializes, but the pattern is the same)¶

import threading
from collections import defaultdict

class LFCounter:
    # Under the GIL, dict ops are atomic but += is not; still need a lock per key
    # OR use a single lock — true lock-freedom isn't available in CPython.
    def __init__(self):
        self._d = defaultdict(int)
        self._lock = threading.Lock()
    def inc(self, key):
        with self._lock:
            self._d[key] += 1
    def get(self, key):
        return self._d.get(key, 0)

Why the second version scales better: the striped per-key counter (LongAdder, atomic int64) eliminates the shard lock entirely on the increment path and spreads contention across cells, while computeIfAbsent/LoadOrStore make the get-or-insert atomic. The Python note is honest: CPython's GIL caps true parallel speedup, so the "lock-free" framing is JVM/Go-specific — in CPython a single lock is the pragmatic answer until free-threaded builds mature.

How to extend this in a follow-up¶

If the interviewer keeps going, the natural next asks are: - Add Total() that's a consistent snapshot — force the discussion to §42's impossibility (you must serialize, so explain why best-effort is the right call). - Bound memory with eviction — introduce per-shard LRU and discuss keeping the policy off the read path. - Make it resize — per-shard incremental rehash consulting both tables, with a forwarding marker (tasks 11–12). - Defend against hash flooding — seeded hash + treeify long chains.

Each extension maps directly to a section in middle.md/senior.md/professional.md, so you can speak to the trade-offs with confidence rather than improvising.

Next step: tasks.md — graded hands-on tasks (beginner → advanced) in Go, Java, and Python.