Concurrent HashMap

Overview

Build a hash map that many threads can read and write at the same time without corrupting it. The simple answer is one big lock around the whole map, but that serializes every operation and kills throughput. The goal is to let operations on unrelated keys proceed in parallel.

The standard technique is lock striping: split the table into N independent segments, each with its own lock. A key maps to a segment by its hash, so a put on one segment never blocks a put on another. This is the core idea behind a real ConcurrentHashMap — fine-grained locking instead of one coarse lock.

Interfaces

class ConcurrentHashMap:
    def __init__(self, num_segments=16):
        self._segments = [Bucket() for _ in range(num_segments)]
        self._locks = [Lock() for _ in range(num_segments)]

    def _segment(self, key):
        return hash(key) % len(self._segments)

    def put(self, key, value):
        i = self._segment(key)
        with self._locks[i]:
            self._segments[i].put(key, value)

    def get(self, key):
        i = self._segment(key)
        with self._locks[i]:
            return self._segments[i].get(key)

    def remove(self, key):
        i = self._segment(key)
        with self._locks[i]:
            self._segments[i].remove(key)

    def size(self):
        # sum each segment's count — acquire all locks for an exact snapshot
        ...

Each segment is its own small map guarded by its own lock. Two threads touching keys in different segments run fully in parallel; only keys colliding in the same segment contend.

Inputs and outputs

• Input: put, get, and remove calls from many threads.
• Output: correct values with no lost updates or corrupted buckets, with far more concurrency than a single global lock.

Requirements

• Operations on different segments proceed concurrently.
• Each segment's internal state is only touched while holding that segment's lock.
• size and other whole-map views must define their consistency — an approximate count needs no global lock; an exact one must hold all segment locks.
• Choosing the segment count trades memory and lock overhead against parallelism.

Examples

m = ConcurrentHashMap(num_segments=16)

m.put("a", 1)     # segment hash("a") % 16
m.put("z", 26)    # likely a different segment — runs in parallel with the above

m.get("a")        # 1
m.remove("a")
m.get("a")        # None

Follow-ups

• A segment gets hot and its load factor climbs. How would you resize just that segment without freezing the rest of the map?

• Reads of the same segment still block each other. When would read-write locks help here, and when would they just add overhead?

• How would you make compute_if_absent atomic so two threads never both insert the same key?

• And more...