Build a Hash Map From Scratch

The contract

The last two lessons described the mailroom clerk from the outside — the word-trick, the hanging hooks, moving day. Now we build the clerk's whole system ourselves, by hand, and give it four jobs: file a package, find a package, throw one away, and always know how many are currently sitting in the cabinet.

We build a string-keyed map with the full core API — get, set, delete, size — using separate chaining (the hanging-hook blueprint), the polynomial hash from lesson 1 (the clerk's word-trick), and doubling at α = 1 (moving day, triggered the moment the cabinet hits one package per slot on average). Everything in the previous two lessons becomes a line of code you can point at.

class HashMap:
    def __init__(self) -> None:
        self._num_buckets = 8
        self._size = 0
        self._buckets: list[list[tuple[str, object]]] = [
            [] for _ in range(self._num_buckets)
        ]

    def __len__(self) -> int:
        return self._size

    def _hash(self, key: str) -> int:                 # polynomial hash
        h = 0
        for ch in key:
            h = (h * 31 + ord(ch)) % 1_000_000_007
        return h

    def _bucket(self, key: str) -> list[tuple[str, object]]:
        return self._buckets[self._hash(key) % self._num_buckets]

    def get(self, key: str, default=None):
        for k, v in self._bucket(key):                # scan ONE chain
            if k == key:
                return v
        return default

    def set(self, key: str, value) -> None:
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)              # overwrite existing
                return
        bucket.append((key, value))                   # new entry
        self._size += 1
        if self._size > self._num_buckets:            # α > 1 → resize
            self._resize()

    def delete(self, key: str) -> bool:
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = bucket[-1]                # swap-remove: O(1)
                bucket.pop()
                self._size -= 1
                return True
        return False

    def _resize(self) -> None:
        old_buckets = self._buckets
        self._num_buckets *= 2                        # doubling — amortized O(1)
        self._buckets = [[] for _ in range(self._num_buckets)]
        for bucket in old_buckets:                    # re-file EVERY entry
            for key, value in bucket:
                self._buckets[self._hash(key) % self._num_buckets].append(
                    (key, value)
                )

Read the code against the theory

• Every operation begins hash → mod → bucket — the clerk's three-step dance: look at the name, run the word-trick, go straight to that slot. This is the "compute the address" idea, verbatim.
• set checks the hook before appending — the clerk never blindly throws a package onto a hook. They first flip through that one hook's existing packages to see if this person already has one filed (then they swap the message for the new one); only if there's no match do they hang a new package at the end. A map holds one value per key, and that check is bounded by chain length, i.e. by α.
• delete uses swap-remove — when the clerk needs to remove a package from a hook, they don't slide every other package down to close the gap. They grab the very last package on that hook, use it to fill the hole left by the one being removed, and pop the emptied hanger off the end. Since the order on a hook never mattered, this works: O(1) instead of the shifting cost an ordered array would pay (Module 4's lesson, exploited).
• Resize doubles and re-files — moving day: % self._num_buckets with the new m sends every package to a new home; the amortized- doubling theorem prices it.
• What's NOT here: per-entry order. Walking the cabinet's slots left to right reads packages in whatever order the word-trick happened to assign them — nothing to do with delivery time. Real Python/JS dicts add an insertion-order layer on top of this.

Try it mentally: insert 9 string keys. The 9th crosses α = 1 with 8 buckets, triggering a resize to 16 — one O(9) rehash, then calm until 17.

One more shape: the hash set

Sometimes you don't care what's inside an envelope — you just want to know who has come through the mailroom. The clerk can hang simple name tags instead of full packages on the exact same cabinet: that's a hash set, membership without payload, built from the identical machinery above. A later lesson (The Four Hash Patterns) gives it the full treatment — for now, just know it's this map with the value column dropped, not a different structure.