📺 Prefer to watch? 90-second YouTube Short · 💬 Telegram
Originally published on software-engineer-blog.com.
Two hundred thousand users in a list. A login handler that looks for one email. It works, it passes review, and it costs 4.4 milliseconds — which sounds like nothing until two thousand people sign in per second and the box is suddenly doing 8.8 CPU-seconds of work every second. Nothing crashes. Nothing shows up in the logs. The service just stops answering.
The identical lookup out of a Python dict takes 71 nanoseconds. About 62,000 times faster, on the same data and the same machine — and not because the dictionary searches faster.
- Mental model: A hash table never searches. It computes where the answer lives. The list looks at a hundred thousand rows; the dictionary looks at one.
This is unit 11 of "the missing CS degree", and it is the one data structure worth understanding properly, because you already use one in every dict, every set, and every "have I seen this before" check you have ever written.
The code you would write first, and it is not wrong
users = load_users() # 200,000 rows, in a plain list
def find_user(email):
for u in users: # one string compare, per row, in order
if u["email"] == email:
return u # average: 100,000 comparisons
return None # worst case: all 200,000
# $ python bench.py
# find_user(...) 4.419 ms <- per login, average row
# 2,000 logins/second -> 8.8 CPU-seconds of work, per second
There is nothing bad in there. It is correct, it is readable, and for a list of twenty it is the right answer. The problem is the shape of the cost: double the users, double the work, every time, forever. That shape is called O(n), and changing it is the entire reason hash tables exist.
Build one, do not import one
The whole idea fits in nine lines, and only one of them matters:
# toytable.py — the whole idea, in nine lines
class HashTable:
def __init__(self, size=8):
self.buckets = [[] for _ in range(size)] # 8 empty slots
self.n = 0 # how many keys we hold
def _index(self, key): # <- THIS is the hash table
return hash(key) % len(self.buckets) # any key -> 0..7
def get(self, key):
for k, v in self.buckets[self._index(key)]: # ONE slot. never the rest.
if k == key:
return v
raise KeyError(key)
hash() is built into Python: hand it a string, it hands back a large integer. Modulo the number of buckets folds that integer down into the range 0 to 7. Key in, slot number out — that one line is the hash table. Everything else in the file is bookkeeping.
Note what get does not do: it never touches the other seven slots. That is where the 62,000x comes from.
Eight names, eight slots — and the collision is not a bug
You are folding billions of possible numbers into eight slots. Of course two of them land in the same place:
h("grace") = 98,615,224 -> % 8 = 0
h("alan") = 2,996,632 -> % 8 = 0
h("edsger") = 2,987,424,544 -> % 8 = 0
Three keys, one slot. Meanwhile slots 2, 3 and 5 got nothing at all. Neither of those is a defect — it is arithmetic. The question is never how to avoid a collision. It is what you do when one happens.
The answer here is chaining: a slot does not hold one entry, it holds a little list.
# toytable.py — set: the two lines that resolve a collision
def set(self, key, value):
bucket = self.buckets[self._index(key)]
for pair in bucket:
if pair[0] == key: # this exact key is already in the slot
pair[1] = value # so it is an update, not an insert
return
bucket.append([key, value]) # a DIFFERENT key, same slot: it queues up
self.n += 1
# >>> ht.buckets[0]
# [['grace', 2], ['alan', 4], ['edsger', 5]] <- three keys, one slot
# >>> ht.get('alan')
# 4 <- 2 compares, not 200,000
All of collision handling is that one append. Getting a key back means: the right slot, then a short walk down its list. Short is the word doing the work — two or three, not two hundred thousand.
Load factor: the number that decides whether any of this stays fast
A hash table is fast while the chains are short. The load factor is what keeps them short:
load factor = keys stored ÷ slots available
Eight keys in eight slots is a load factor of 1.0. It is the average number of keys sitting in a slot, which is the same thing as the number of comparisons a lookup costs. So it is not a tidiness metric — it is your lookup cost, written as one number.
Measured over 100,000 real keys:
| load factor | average chain | longest chain |
|---|---|---|
| 0.75 | 1.4 | 7 |
| 1.0 | 1.6 | 7 |
| 2.0 | 2.3 | 10 |
| 8.0 | 8.0 | 21 |
Eight times as crowded costs eight times the comparisons, and it degrades smoothly — which is exactly why nobody notices until it matters.
This is also why the textbook writes O(1) as "amortised, average case". The average case is a statement about the load factor, and the load factor is not a fact about your data. It is something you actively keep down.
The resize, and why every key has to move
# toytable.py — the four lines that keep the O(1) true
def set(self, key, value):
...
bucket.append([key, value])
self.n += 1
if self.n / len(self.buckets) > 0.75: # over three quarters full
self._resize() # so make the table bigger
def _resize(self):
old = self.buckets
self.buckets = [[] for _ in range(len(old) * 2)] # twice as many slots
for bucket in old:
for k, v in bucket:
self.buckets[self._index(k)].append([k, v]) # EVERY key moves
It cannot copy the pairs across into the same positions. _index divides by the number of buckets, and that number just changed:
h("grace") % 8 = 0
h("grace") % 16 = 8 <- same key, same hash, different slot
So every key belongs somewhere new, and re-inserting all of them is what "rehashing" means. That occasional O(n) pass, spread over all the cheap inserts that preceded it, is the amortised in "amortised O(1)".
On our eight keys, the three-deep chain in slot 0 became a one and a two. That is all a resize ever does: it buys the chains room by making the divisor bigger.
Chaining vs open addressing — you use both every day
| Chaining | Open addressing | |
|---|---|---|
| On a collision | The slot holds a list; the new pair is appended to it | Probe on to another slot by a fixed rule — there are no lists |
| Memory layout | Every entry costs a pointer, and the chain is scattered | Cache-friendly — probing stays inside one block of memory |
| Deleting | Simple: unlink it from the list | Genuinely awkward — you have to leave a tombstone behind |
| Who uses it | Our toy table, Java's HashMap; Go chains overflow buckets |
Python's dict, and Ruby's Hash
|
Neither one avoids collisions. Nothing avoids collisions. They are two different answers to "this slot is taken".
When O(1) becomes O(n) — and the attack built on it
One bad hash function turns your hash table straight back into the list you replaced:
| 4,000 keys | longest chain | lookup |
|---|---|---|
| an ordinary hash | 4 | 0.4 µs |
| every key forced into slot 0 | 4,000 | 74.5 µs |
186 times slower. Same table, same keys, same machine — the structure is identical, only the hash changed.
And if an attacker can guess your hash function, they can send you exactly those keys on purpose. That is a real denial-of-service class, and it is why CPython randomises the hash of every string at start-up.
Three details about the dict you already use
- CPython uses open addressing, not chaining, and grows the table at roughly two thirds full.
- Since 3.7 a dict keeps insertion order — that comes from a second, compact array of indices, not from anything about hashing.
- A key has to be hashable, which in practice means immutable:
{[1, 2]: "x"}raisesunhashable type: list. -
hash(1),hash(1.0)andhash(True)are all1— so{1: "a", 1.0: "b", True: "c"}is a dict with one key, holding"c".
The same trade-off in LLM serving
This is not a legacy-backend concern that AI work has moved past. The inference stack is held together by hash tables, and by their one limitation:
- Prefix / KV-cache reuse. Serving engines like vLLM cache blocks of KV state and look them up by a hash of the token prefix. Two requests that share an opening system prompt hit the same block and skip recomputing it. That lookup has to be O(1) on every single request, so it is exactly the structure above — and the "hash keys must be deterministic" rule is why block hashing has to be stable across replicas or the cache silently stops hitting.
- Tokenizer vocabulary. Every token-to-id lookup is a hash map, run tens of thousands of times per second. It is the definition of "cheap hash function matters".
- Exact-match response caching and dedup. "Have I answered this exact prompt before?", "have I already embedded this chunk?" — both are set membership, which is the one thing a hash table is unbeatable at.
- And what it cannot do is why vector search exists. Hashing deliberately destroys the relationship between keys. A semantic cache needs the nearest prompt, not the identical one, and "nearest" is precisely the query a hash table cannot answer. That is why retrieval runs on an ANN index and not a dict — the same reason a database index is a B-tree.
The rule transfers exactly: hash for identity, something ordered for proximity.
When a hash table is the wrong choice
| Unbeatable at | Cannot do it at all |
|---|---|
| Is this exact key present? | Every key between 10 and 50 |
| The value for this exact key | The smallest key, or the next key after this one |
| Have I already seen this? | Anything starting with "sm", or sorted output |
| Dedup, caches, sets, indexes by id | The nearest match, or a predictable worst case |
Hashing throws away order to buy you speed, and sometimes order was the thing you needed. It costs memory, too: a thousand integers in a list is about 8 kilobytes; a thousand pairs in a dict is about 37.
The whole thing in one breath
A hash table turns a key into a slot number by arithmetic instead of searching, which is why a dict lookup is 71 nanoseconds where a list scan is 4.4 milliseconds. Folding a huge number space into a small array must produce collisions, so a slot holds a short chain (or probes on to the next slot). Chains stay short only while the load factor stays low, which is why the table doubles at about three quarters full and rehashes every key — the divisor changed, so every key belongs somewhere new. That occasional O(n) pass is the "amortised" in amortised O(1), and a bad or attacker-chosen hash collapses the whole thing back to O(n).
Verdict
Reach for a hash table by default for anything keyed by identity: lookups by id, membership, dedup, caches. It is the best constant-factor win in everyday code, and the mental model is one sentence — it computes the address, it does not search for it.
Reach for something else the moment the question involves order or proximity: ranges, prefixes, min/max, sorted scans, nearest match. Name the replacement out loud — a B-tree, a sorted array, a trie, an ANN index — because in an interview, and in a design review, that is the half of the answer most people leave out.
Watch the full 13-minute walkthrough for the table built line by line, the collision and the resize on screen, and five real interview questions with an answer skeleton for each — or the 2-minute version for the short of it.
Top comments (0)