Hash Map Locks

Resources

• https://en.wikipedia.org/wiki/Concurrent_hash_table

Get this in interview questions pretty often. How do you lock a hash map?

size_t idx = std::hash<std::string>{}(key) % table.size();

• See String Hashing for how we hash

1) Easiest correct answer: one global lock

One mutex for the whole map.

• get/put/erase all lock it.
• Correct, simple.
• Downside: no parallelism.

If they push: “can we do better?” → go to #2.

2) Better: reader/writer lock on the whole map

Use a single shared_mutex (RW lock):

• get() takes shared lock (since it’s read-only, readers can share that lock), see shared_lock
• put/erase() takes unique lock
• Great when reads dominate.

Downside: still blocks all writers globally; contention if lots of writers.

What about open addressing (linear probing)?

This is where “per-key mutex” answers often break.

With linear probing, keys don’t “live in their own bucket.” A write can affect a run of slots, and deletion can require tombstones or shifting entries.

You have a few options:

Option A (interview-friendly): lock striping over ranges of slots

• Locks protect contiguous segments of the array.
• For an operation, you lock the stripe(s) that your probe sequence touches.
• To avoid deadlock, lock stripes in increasing order.

This is workable but can lock more than you want.

Option B (advanced): CAS/atomics per slot (lock-free-ish)

• Each slot is an atomic state machine: EMPTY / OCCUPIED / TOMBSTONE
• Inserts use compare_exchange to claim a slot.
• Reads are mostly lock-free.
• Deletes mark tombstones.
• Resizing becomes very complex (needs epoch-based reclamation / RCU-like scheme).

In most interviews: mention it as an advanced path, but don’t build it unless asked.