How Would You Design a Concurrent Hash Map?
Learn how to design a thread-safe concurrent hash map with segment locking, lock-free reads, and cooperative resizing.
Expected Interview Answer
A concurrent hash map achieves thread-safe reads and writes at scale by splitting the table into independently lockable segments (or per-bucket locks) instead of guarding the whole map with a single lock, so unrelated keys in different segments can be modified in parallel.
Classic designs like Java's ConcurrentHashMap divide the bucket array into a fixed number of segments, each with its own lock; a write only locks the segment containing its key's bucket, so writes to different segments proceed truly in parallel, while reads are typically lock-free using volatile reads and happens-before guarantees. Resizing is the hardest part: the map must grow the bucket array without blocking all readers, usually by having threads cooperatively help migrate entries from the old table to the new one bucket by bucket. Modern implementations increasingly use CAS-based bucket updates instead of locks for simple operations like insert-if-absent, falling back to fine-grained locks only for tree-ified buckets or complex updates. The core tradeoff is granularity: more segments/locks means more parallelism but higher memory and coordination overhead, while too few segments recreates the single-lock bottleneck.
- Parallel writes to different segments/buckets
- Lock-free or near lock-free reads
- Avoids the single-lock bottleneck of a synchronized map
- Scales throughput with core count under low contention
AI Mentor Explanation
A concurrent hash map is like a stadium with many separate ticket counters instead of one single window serving every fan. Each counter handles its own range of seat numbers, so two fans buying tickets for different sections never wait on each other, only fans wanting the same section's counter queue briefly. When the stadium expands and adds more counters, staff migrate bookings counter by counter without shutting the whole box office down. This segmented design is why thousands of fans can buy tickets simultaneously instead of forming one long line at a single register.
Step-by-Step Explanation
Step 1
Partition into segments/buckets
Split the underlying table into independently lockable segments or use per-bucket locks so unrelated keys never contend.
Step 2
Lock only the target segment on write
A put/remove locks just the segment owning that key's hash, letting other segments proceed in parallel.
Step 3
Make reads lock-free where possible
Use volatile reads and happens-before guarantees so gets do not need to acquire any lock at all.
Step 4
Resize cooperatively
On growth, migrate entries bucket by bucket with helper threads assisting the transfer instead of blocking the whole map.
What Interviewer Expects
- Explain segment or bucket-level locking instead of a single global lock
- Distinguish lock-free reads from locked writes
- Describe the resizing challenge and a cooperative migration strategy
- Name a real implementation (Java ConcurrentHashMap, Go sync.Map) as reference
Common Mistakes
- Proposing a single global lock around the whole map (defeats the purpose of concurrency)
- Forgetting that resizing under concurrent access is the hardest part of the design
- Assuming reads always need a lock even for immutable/volatile-backed structures
- Not discussing the granularity tradeoff between more locks (more parallelism) and overhead
Best Answer (HR Friendly)
“I would design a concurrent hash map by splitting the table into independent segments, each with its own lock, so writes to different parts of the map can happen at the same time instead of one thread blocking everyone. Reads would avoid locking entirely where possible, and resizing would migrate data gradually instead of freezing the whole structure.”
Code Example
import threading
class SegmentedConcurrentMap:
def __init__(self, num_segments=16):
self.num_segments = num_segments
self.segments = [dict() for _ in range(num_segments)]
self.locks = [threading.Lock() for _ in range(num_segments)]
def _segment_for(self, key):
index = hash(key) % self.num_segments
return self.segments[index], self.locks[index]
def put(self, key, value):
segment, lock = self._segment_for(key)
with lock:
segment[key] = value
def get(self, key):
segment, _ = self._segment_for(key)
return segment.get(key) # read without locking (simplified)
def remove(self, key):
segment, lock = self._segment_for(key)
with lock:
segment.pop(key, None)Follow-up Questions
- How does Java's ConcurrentHashMap handle resizing without blocking all threads?
- Why can reads often avoid acquiring a lock while writes cannot?
- How would you choose the right number of segments for a given workload?
- What happens to a concurrent hash map's performance under extreme hash collisions?
MCQ Practice
1. What is the main advantage of segment/bucket-level locking over a single global lock?
Segmenting the lock means only writes to the same segment contend, letting unrelated keys be updated truly in parallel.
2. What is the hardest part of designing a concurrent hash map?
Growing the bucket array while other threads read and write requires cooperative, incremental migration to avoid a full stop-the-world pause.
3. Why can gets in a well-designed concurrent hash map often avoid locking?
Using volatile/atomic references for bucket heads lets readers safely observe the latest published state without acquiring a lock, as long as writers publish changes atomically.
Flash Cards
What replaces a single global lock in a concurrent hash map? — Segment-level or bucket-level locks, so unrelated keys don't contend.
Can reads in a concurrent hash map usually avoid locking? — Yes, typically via volatile reads and happens-before guarantees.
What is the hardest design challenge? — Resizing the table without blocking all concurrent readers and writers.
Name a real-world concurrent hash map implementation. — Java's ConcurrentHashMap (segment/bucket-locked) or Go's sync.Map.