Building a hash map from scratch

A dictionary lookup is described as O(1), and that claim tends to get filed under magic. It is not magic, and the mechanism is simple enough to build in an afternoon. Building it is worth the afternoon, because everything people find surprising about hash maps later — why lookup degrades, why keys must be immutable, why deleting an entry is harder than adding one — falls straight out of the construction.

So we will build one, in stages, each stage fixing something the previous one got wrong.

The problem an array almost solves

An array gives you instant access by position. Ask for element 4,000 and the machine computes an address and reads it, with no searching involved. That is as fast as data access gets.

The catch is that you rarely know the position. You know a username, an order reference, a country code. Searching an array for a matching value means looking at the entries one by one, which is O(n) — fine for ten items, ruinous inside a loop over a million.

What you want is the array's instant access, addressed by an arbitrary key rather than a position. Hashing is the bridge: a function that turns a key into a number, which you then reduce into the range of your storage.

def slot(key, nbuckets):    return hash(key) % nbuckets

That is the whole idea. Everything after this is dealing with the consequences.

What makes a hash function good, and how a bad one fails

A hash function must be deterministic (the same key always gives the same number, or you could never find anything again) and fast (it runs on every single operation). The third requirement is the interesting one: it should scatter similar inputs to dissimilar outputs.

Here is a hash that looks reasonable and is not — summing the character codes:

def naive_hash(s):    return sum(ord(c) for c in s)

Addition does not care about order, so every anagram collides. Grouping fifteen words by this hash:

432 -> ['evil', 'vile', 'live', 'veil', 'levi']454 -> ['stop', 'tops', 'pots', 'opts', 'spot']655 -> ['listen', 'silent', 'enlist', 'tinsel', 'inlets']15 words landed in 3 distinct slotsbuilt-in hash mod 1000: 15 distinct slots

Fifteen keys into three slots. Every lookup in those groups now walks a five-element chain, and the constant-time promise is gone.

One honest caveat, because it changes how you should test. Run that same naive hash over two hundred randomly generated six-letter strings and it spreads them across sixteen buckets about as evenly as the built-in one does. On random input it looks perfectly fine. Real keys are not random — they are permutations, sequential identifiers, values sharing prefixes and suffixes, names drawn from the same alphabet. A hash function must be judged on keys shaped like the ones you will actually store, and that is the mistake the random test would have let you make.

Collisions are arithmetic, not bad luck

Even with an excellent hash function, collisions are guaranteed. There are vastly more possible keys than buckets — infinitely many strings, a few thousand slots — so by the pigeonhole principle some keys must share. Collisions are not an edge case to be minimised into irrelevance; handling them is a required part of the design.

Two families of solution. Separate chaining keeps a list per bucket and appends colliding entries to it. It is easy to reason about and easy to delete from, at the cost of a pointer indirection per entry and worse memory locality.

class ChainedMap:    def __init__(self, capacity=8):        self._buckets = [[] for _ in range(capacity)]    def __setitem__(self, key, value):        bucket = self._buckets[hash(key) % len(self._buckets)]        for i, (k, _) in enumerate(bucket):            if k == key:                bucket[i] = (key, value)      # replace, do not append                return        bucket.append((key, value))    def __getitem__(self, key):        bucket = self._buckets[hash(key) % len(self._buckets)]        for k, v in bucket:            if k == key:                return v        raise KeyError(key)

Chaining has a property worth noticing: it tolerates a load factor above 1. You can store more entries than buckets, because each bucket holds a list. Performance degrades as chains lengthen, but nothing breaks. Open addressing cannot exceed its capacity at all — the table is the storage — so it must grow before it fills.

Open addressing stores everything in the array itself: if a slot is taken, probe forward until you find a free one. It has better cache behaviour, since a probe sequence walks contiguous memory. It also has a subtlety that makes deletion genuinely tricky, which is the next section.

Which to choose in practice? Open addressing wins when entries are small and you care about speed, because a probe sequence reads consecutive memory and the processor prefetches it for free, whereas chasing list nodes around the heap costs a cache miss each hop. Chaining wins when entries are large, when deletions are frequent, or when you cannot predict the load — it degrades gracefully rather than requiring careful capacity management. Most standard library implementations pick open addressing for exactly the cache reason, and absorb the extra complexity that the next section is about.

Why deleting is harder than inserting

With linear probing, a lookup stops at the first empty slot — that is what tells it the key is absent. Now delete a key from the middle of a probe chain and mark its slot empty. Every key stored after it in that chain becomes unreachable: the search hits your new gap, concludes the key is not present, and gives up on entries that are sitting right there.

The fix is a tombstone: a marker meaning "occupied once, empty now". Lookups probe past it; insertions may reuse it. That distinction between "never used" and "used and freed" is the piece beginners omit, and the resulting bug is the worst kind — data silently invisible rather than an error.

Here is the full implementation with tombstones and growth:

_MISSING = object()      # never used_TOMBSTONE = object()    # used, then deletedclass HashMap:    def __init__(self, capacity=8):        self._capacity = capacity        self._keys = [_MISSING] * capacity        self._values = [None] * capacity        self._size = 0       # live entries        self._used = 0       # live entries + tombstones    def _slot(self, key):        """Return (index, found). Reuses the first tombstone on insert."""        i = hash(key) % self._capacity        first_tomb = -1        while True:            k = self._keys[i]            if k is _MISSING:                return (first_tomb if first_tomb != -1 else i), False            if k is _TOMBSTONE:                if first_tomb == -1:                    first_tomb = i            elif k == key:                return i, True            i = (i + 1) % self._capacity

And the operations on top of it. Note that deletion writes a tombstone rather than clearing the slot:

    def __setitem__(self, key, value):        i, found = self._slot(key)        if found:            self._values[i] = value            return        if self._keys[i] is not _TOMBSTONE:            self._used += 1        self._keys[i] = key        self._values[i] = value        self._size += 1        if self._used * 4 >= self._capacity * 3:      # load factor 0.75            self._resize()    def __delitem__(self, key):        i, found = self._slot(key)        if not found:            raise KeyError(key)        self._keys[i] = _TOMBSTONE     # NOT _MISSING: would cut the chain        self._values[i] = None        self._size -= 1

Load factor, and why growing means rehashing

As the table fills, probe sequences lengthen and performance decays — gently at first, then sharply as the table approaches full. The load factor is the fraction occupied, and the standard response is to grow when it crosses a threshold around 0.75.

Why that threshold rather than something tidier? It is a trade between memory and probe length, and the relationship is not linear. At a load factor of 0.5 the average successful probe is short and you waste half your memory. At 0.9 memory use is efficient and probe sequences have grown long enough to hurt; at 0.95 they are severe. Around 0.75 the curve is still shallow while three quarters of the allocation is doing useful work. It is an empirical compromise rather than a derived constant, which is why implementations differ on the exact figure.

One detail in the code above is easy to miss and matters here: the growth check tests _used, which counts tombstones, rather than _size, which does not. Tombstones lengthen probe sequences exactly as live entries do, so a table churning through insertions and deletions can fill with tombstones while _size stays low. Costing growth against live entries alone lets that table degrade to linear scans while its occupancy looks healthy.

Growing is not a copy. The bucket index comes from hash(key) % capacity, and capacity has just changed, so every key belongs in a different place. Every entry must be reinserted:

    def _resize(self):        old = list(self.items())        self._capacity *= 2        self._keys = [_MISSING] * self._capacity        self._values = [None] * self._capacity        self._size = 0        self._used = 0        for k, v in old:            self[k] = v            # rehash into the new capacity

This is why doubling matters rather than growing by a fixed amount. A rehash is O(n), but doubling makes rehashes exponentially rare, so their cost spread over all the cheap insertions is a constant per insertion. That is the amortised O(1) guarantee — most insertions are cheap, a few are expensive, and the average stays flat as the table grows.

Exercising the finished class, including deletion in the middle of a chain and growth:

after 5 inserts: 5 cap 8  gamma -> 2  overwrite beta -> 99 size still 5  after delete gamma: size 4  'gamma' in m: False  delta still reachable -> 3  lookup of deleted key raises KeyError: 'gamma'after 20 more inserts: size 24 cap 64  all 20 survive rehash: True

The line worth pausing on is delta still reachable. That is the tombstone working: delta sits behind gamma in a probe chain, and it survived the deletion. Replace _TOMBSTONE with _MISSING in __delitem__ and that lookup fails while every other test still passes.

Average O(1), worst case O(n), and why that is a security matter

The honest complexity is average-case constant, worst-case linear. The worst case is every key colliding, which turns the table into a single list.

With a decent hash and random keys, that will not happen by accident. It can happen on purpose. If an attacker knows your hash function and can choose your keys — form field names, JSON object keys, query parameters — they can craft thousands of keys that all land in one bucket. Every insertion then walks the whole chain, and an operation you costed as O(1) becomes O(n), making the total O(n squared). A modest number of requests can consume all your CPU.

This was exploited widely enough that language runtimes changed in response: many now randomise the hash seed per process, so an attacker cannot predict which keys collide. It is why hash("abc") can differ between runs of the same program. If you ever write your own hash for untrusted keys, this is the consideration that matters most, and it is a reason to prefer the built-in.

Two rules that follow from the mechanism

Both of these are usually presented as arbitrary language rules. They are consequences of what we just built.

Keys must be immutable. A key's slot is determined by its hash at insertion time. Mutate the key afterwards and its hash changes, so lookups compute a different slot and find nothing — while the entry sits in the old slot, still occupying space, now unreachable:

  before mutation, lookup: stored  after b.v = 2,  lookup: None  but the entry is still there: [(Box(2), 'stored')]

The value was never lost. It became unaddressable. That is why languages either forbid mutable keys outright or leave you to enforce it, and why using a mutable object as a key is a bug even when it appears to work.

Equal objects must have equal hashes. If two keys compare equal but hash differently, they land in different buckets and the map holds both — so a lookup finds whichever slot it computes and your map now has two entries for one logical key. Whenever you define custom equality, define a matching hash from the same fields.

When a hash map is the wrong container

The mechanism explains its own limits. Slots are assigned by hash value, which deliberately destroys any relationship to the key's natural order. So a hash map cannot answer any question about order without examining everything:

• Range queries — every key between two bounds — require a full scan, because neighbouring keys are scattered.
• Smallest or largest key is O(n) for the same reason.
• Sorted iteration means extracting everything and sorting it.
• Nearest key to a value is not expressible at all.

Iteration order deserves a specific warning, because it is a portability trap. Iterating our implementation yields keys in slot order, which is an artefact of hash values, capacity, and insertion history. It looks arbitrary, and it is — but it also looks stable within a single run, which tempts people into relying on it. Insert one more key, trigger a resize, and the order changes completely. Some languages guarantee insertion order for their dictionaries and some explicitly do not; unless yours promises it in writing, treat the order as undefined.

Those are the questions balanced trees and heaps exist to answer, trading the constant-time single lookup for structure that preserves order. If your access pattern is "fetch exactly this key", a hash map is close to unbeatable. If it involves order, ranges, or extremes, you are using the wrong tool and no amount of tuning the load factor will help.