03 — Hash tables

The email asks for this one in writing: implement one using only arrays, in about the space of one interview. It is the single most likely "write this from scratch" request you will get.

Prereqs: 01 · Reading: 7 min · Cards: 12 · Code: code/hashtable.py

The map

A hash table is three decisions stacked on each other, and every interview question about them targets one of the three. First, a hash function turns a key into an integer. Second, that integer is compressed — usually modulo the capacity — into a bucket index. Third, something must happen when two keys land on the same bucket, because by the pigeonhole principle they will.

That third decision is where the subject actually lives. Everything interesting — the deletion trap, the load factor, the worst case, why Python and Java made different choices — follows from how you resolve collisions. Get the three-part framing out loud early and the rest of the conversation has somewhere to hang.

What decides your score here

Finishing the implementation, including the resize. An implementation without a resize is not finished: every operation degrades to linear as it fills. Candidates run out of time on this because they narrate too little and code too much. Rehearse until you can do it in twenty minutes.

The tombstone. If you choose open addressing, deletion is the trap the interviewer is waiting for. Knowing it before they ask is a strong signal; discovering it when they ask is fine; not seeing it at all is the failure mode.

Qualifying the complexity. "A hash table is O(1)" is incomplete. It is O(1) average, O(n) worst case, and the worst case is real rather than theoretical.

Chaining, and why it is the safe choice

Each bucket holds a list of key-value pairs. On put you walk the bucket looking for the key — overwriting if it is already there rather than appending a duplicate, which is the small correctness detail people miss — and otherwise you append. On get you walk and compare. On delete you remove from the list, which is trivial.

It is simple, it tolerates a load factor above one because a long chain is just a longer list, and deletion has no special case. The cost is a pointer per entry, which is memory and, more importantly, poor cache behaviour: every probe is a pointer chase into unrelated memory.

Java 8 added a refinement worth citing: once a bucket passes eight entries it converts the list into a balanced tree, capping the worst case at log n instead of linear. That is a defence against deliberate collision attacks, not just bad luck.

Open addressing, and the trap in it

Everything lives in one contiguous array. On collision you walk forward to the next free slot. No per-node allocation, and every probe touches adjacent memory, so it is cache-friendly — which is why Python's dict and Ruby's hashes use it.

The price is clustering: occupied slots bunch together, and probe sequences grow much faster as the table fills. That is why the load factor has to stay lower, around two thirds rather than three quarters.

And then deletion. You cannot simply blank the slot. Any key that collided and was placed past that slot is found by probing through it — blank it, and those keys become unreachable while still occupying memory. The fix is a tombstone: a marker meaning "something used to be here". Lookups probe through it; insertions may reuse it. The cost is that tombstones accumulate, so the resize threshold has to count them rather than only live entries. There is a test for exactly this in code/test_all.py.

Resizing, which is the part that gets cut for time

When the load factor crosses the threshold, you double the capacity and reinsert everything. You cannot copy the buckets across, because the index depends on the modulus and the modulus just changed.

It costs O(n), but it happens once every n insertions, and because the capacity doubles the total work across n insertions is bounded — so each operation is amortised constant. That is the same argument as list.append in module 01, and saying so links the two topics in the interviewer's mind.

Where the worst case actually comes from

O(n) happens when every key lands in one bucket. That is not a theoretical curiosity: a poor hash function does it accidentally, and an attacker choosing keys does it deliberately. The attack has a name, hash flooding, and the defence is randomising the hash per process — which Python has done since 3.3, controlled by PYTHONHASHSEED. A useful consequence: never persist a Python string hash or sort by it, because it differs between runs.

A good hash function is deterministic, uniform, fast, and has the avalanche effect — flipping one input bit flips about half the output bits. Names worth having: FNV-1a for short strings, MurmurHash3 and xxHash for speed. SHA-256 is far too slow here; keep it for cryptography.

The key contract, and the pattern it enables

A key must be immutable and its hash must be consistent with equality: equal objects must hash equal. Mutate an object after using it as a key and it becomes unreachable, because its hash now points at a different bucket. In Python that means tuples and frozensets work as keys; lists, dicts and sets do not.

That contract is what makes the canonical key pattern work. When the task is grouping equivalent things, the craft is finding a function that maps every equivalent input to the same hashable value. For anagrams it is the sorted string, or better, a tuple of letter counts — linear instead of n log n. That single idea is the whole solution to Group Anagrams, and it generalises far beyond it.

The other pattern worth naming is combining two structures. An LRU cache needs constant lookup and constant reordering, and no single structure gives both — so a hash map points at nodes of a doubly linked list, each covering the other's weakness. Whenever a prompt opens with "Design a…" and names a per-operation complexity, that is the shape of the answer.

Say it

Cover the answers. Out loud, in English.

Now do this

The first one is the point of the module. Do it before the others.

1. Design HashMap — 20 min, timed, no reference. Narrate the three pieces, pick a strategy out loud, include the resize. Repeat on another day until twenty minutes is comfortable.
2. Group Anagrams — 15 min. The canonical key.
3. Subarray Sum Equals K — 25 min. Say out loud why a sliding window does not work here.
4. LRU Cache — 30 min. Two structures.

Stop when you can build a working hash table with resize in twenty minutes, narrating, without looking anything up.