Concurrent HashMap

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.

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
        ...

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?

• And more...