07Hash tables

In Chapter 6 we lined our values up in a row of slots and reached each one by its position — box 0, box 1, box 2. That works right up until the day you know a song's name but not its number. Then a list has only one move left: walk the whole row asking is it you? is it you? — a million questions for a library of a million tracks. This chapter kills that walk. I want to go slowly, because there's a genuinely beautiful trick here that most tutorials skip past. Here's the plan. We hand every key to hash() and watch it collapse into a single number. That number picks a bucket. We see what happens when two keys land in the same one. And we find out why the whole thing quietly trades RAM for speed. The one question we keep coming back to is the one that matters: how does a dict jump straight to a value without ever scanning for it? By the end you'll ask for library["Titanium"] and get 245 back in a single hop. You'll know exactly why a list can never be a key while "Blinding Lights" always can. And you'll rip the values out of a dict and find a set was hiding inside it the whole time. There's no magic in any of it — just arithmetic standing in for a search.

01The problem: finding one song in a million

Let's start with the one thing a list simply cannot do. Picture your whole music library — a million tracks — living in a list of (title, seconds) pairs. Now answer one small question: how long is "Blinding Lights"? You know the name. The list doesn't care. It only ever knows positions — box 0, box 1, box 2 — never names. So watch what Python is forced to do. It walks the row, holds each pair up to the light, and asks the same dull question: is it you? is it you? is it you? The pair you want could sit anywhere, so in the worst case it asks all one million times before it finds the match. And here's the sting: the answer isn't remembered. Ask for that same song's length a second time and you pay the full million-question toll again. That cost grows with the pile, every single time, and it has a name: O(n).

A dictionary (dict) refuses to play that game. Instead of going position by position, it stores key → value pairs and fetches by key in a single move — no walking, no asking. Each key is unique: a label that points at exactly one value. Hand the dict a key and the value falls out. You write one in curly braces, with a colon gluing each key to its value and commas separating the pairs. (Since Python 3.7 a dict also remembers the order you inserted things in — a small kindness the old ones didn't offer.) That one-move cost has its own name, and it's the whole reason this chapter exists: O(1), the same tiny price whether the library holds ten songs or ten million. And you've been leaning on one all along without seeing it. The name→object bindings from chapter 3 — your module's globals, and every object's attributes — are themselves stored in a dict that maps a name-string to the object's heap address. Every time you write x = 5 and later read x, a hash table is doing exactly the lookup this chapter is about to take apart.

song = {"title": "Blinding Lights", "artist": "The Weeknd", "seconds": 200}

print(song["artist"])                # The Weeknd — one jump, no scan
print(song["seconds"])               # 200

# song["genre"]                      → KeyError: 'genre'  (crash!)
print(song.get("genre", "unknown"))  # unknown — the safe fetch

Two ways to ask. song["artist"] demands the value and insists the key exists. Reach for a key that was never there, like "genre", and the dict doesn't shrug and hand back a blank — it raises a KeyError and stops the program cold. When you're not sure a key is present, song.get("genre", "unknown") is the gentle version: it returns the value if the key is there, and your fallback if it isn't. No crash.

"One jump" and "a million questions" are easy to say. It's another thing to feel the gap. Grow the library below and watch which cost moves.

The dict's entire superpower rests on turning a key into a slot number without looking. So how does "Blinding Lights" — a string, not a number — become an address? Meet hash(): every key becomes a number. →

02hash(): every key becomes a number

Chapter 0 left you with a superpower and a catch. The superpower: RAM can leap to box 6012 without walking the street, because the address is a calculation, not a search — start + i × 4 and you're there. The catch: that trick only works when your key already is a number. A list is happy, since lengths[3] is arithmetic. But you don't want to ask for song #3. You want to ask for "Blinding Lights", and a title is not a house number. So here's the move that unlocks the whole chapter. What if we could turn any key — a string, a pair, anything — into a number first, and then do the address arithmetic?

That converter is a hash function. Feed it any object and it doesn't just glance at it. It walks every byte of the contents, mixing each one into a running accumulator, so a single changed character avalanches into a completely different result. A string is folded byte by byte over its UTF-8 encoding (CPython uses an algorithm called SipHash); a tuple folds together the hashes of its own elements, in order, into one number. Because the fold reads the contents and nothing else, it obeys one iron rule: the same value always comes out as the same number, every time you ask, within one run of your program. For the same reason, equal contents give equal numbers, while ("a","b") and ("b","a") come out different, because order is folded in too. Python hands you the converter as a built-in called hash(). The surprising part, the part that makes dictionaries possible, is that it works on things that look nothing like numbers.

# every value crunches down to one integer
print(hash(245))                        # 245  — small ints hash to themselves
print(hash("Titanium"))                 # a huge signed int — a new one every run
print(hash(("Titanium", "David Guetta")))  # tuples hash too — one number for the pair
print(hash([200, 245]))                  # TypeError: unhashable type: 'list'  (why? see below)

Now the leap makes sense. A dict keeps an internal array of slots — call them buckets. To store "Blinding Lights" → 200, Python computes hash("Blinding Lights"), then folds that gigantic number down onto a real slot by taking the remainder modulo the number of buckets. A brand-new dict starts with 8 buckets, and a remainder modulo 8 can only ever be 0–7, so any 19-digit hash collapses onto a bucket that actually exists. What the bucket then stores is not the song and its length. Picture it holding two of chapter 0's 8-byte addresses: one pointing at the key object, one at the value object. (That two-pointers-in-the-bucket image is a labelled simplification. Since CPython 3.6 the bucket actually stores a small integer index into a separate dense array, and it is there that the key-pointer, the value-pointer, and a cached copy of the hash live side by side — a later deeper cut opens it up. What a bucket remembers is still just where to find the key and value; only the indirection is glossed here.) The string "Blinding Lights" and the int 200 stay wherever they were built on the heap; the bucket just remembers where to find them. To read the value back, Python runs the exact same arithmetic — same hash, same remainder, same bucket — and follows the value's address. The key becomes an address, after a little math.

Eight buckets, endless possible keys — you saw 200 and 8 crash into the very same slot. When two keys want one bucket, what does the dict actually do about it? →

03Buckets and collisions

A hash function hands every key a bucket number, and lookups become a single jump instead of a search. Beautiful — until two keys are handed the same number. That's a collision, and here's the uncomfortable truth: collisions are not bad luck you can engineer away. There are only ever a handful of buckets and effectively unlimited possible keys. So by sheer pigeonhole logic — more pigeons than holes — some pair must share. Squeeze 200 songs into 128 buckets and two of them collide with certainty, no matter how clever the hash. A hash table that pretended collisions couldn't happen would be one that sometimes lost your data.

Python's answer is refreshingly blunt: if your home bucket is already taken, probe. Step to another slot, and keep stepping until a free one turns up, wrapping past the end back to bucket 0 if you run off the edge. The newcomer simply takes a detour. The payoff comes later, at lookup, which retraces the identical steps: hash the key, jump to the home bucket, ask "is this my key?", and if not, step exactly as insertion did — until it finds the key or hits an empty slot. Same recipe in, same recipe out. That symmetry is the whole reason the detour is safe.

But wait — if the address was computed from the key, why does lookup bother asking "is this my key?" at all? Because a collision may have parked a different key in your home bucket. Arriving at bucket 0 doesn't prove you found your song's length; it might be a squatter that hashed there first. So the table does exactly one kind of comparison — an equality check, == — to confirm the key it found is genuinely yours and not an impostor sharing the address. That's the only comparing a dict or set ever does, and on a healthy table it happens once, maybe twice. One hash, a jump, one ==: that is what "O(1)" is actually made of.

# a song's length IS its own hash — so its bucket is pure arithmetic
print(hash(200))          # 200   — small ints hash to themselves
print(200 % 8)            # 0     — "Blinding Lights" lands in bucket 0
print(248 % 8)            # 0     — "Get Lucky" wants that SAME bucket → collision
print(hash("Titanium"))   # a huge, salted number — different every run

Notice the last line. Integer keys hash to themselves, so their buckets are perfectly reproducible. String keys get a salted hash that changes every time Python starts, precisely so an attacker can't hand-craft keys that all collide. That's why the interactive below hashes song lengths (plain integers): the arithmetic is honest and you can check it by hand. Drag the slider and insert five songs one at a time, and watch two of them fight for a bucket.

Probing is cheap while free slots are easy to find — but every insertion crowds the table, probes lengthen, and O(1) starts rotting toward O(n). Python refuses to let that happen: the moment the table drifts past about two-thirds full it quietly builds a bigger one. That trade — spend RAM, keep the speed — is the load factor. →

04Load factor: RAM traded for speed

You've seen the bucket trick: hash(key) % size turns a key straight into a slot number, so a lookup is one jump instead of a search. But a fixed row of buckets has an obvious problem. Keep pouring keys in and it fills up, and the moment two keys want the same slot the dict has to probe onward to the next free one. The fuller the table, the longer those probes. So the dict watches one number like a hawk: the fraction of buckets in use, its load factor. Let the load climb too high and the crisp one-jump lookup rots into a long shuffle past occupied slots.

CPython's rule is blunt and effective: once about two-thirds of the buckets are spoken for, the dict allocates a fresh table twice as big and re-hashes every existing key into it. Bigger table, new % size, a new home computed for everyone. That rebuild is real work, O(n) in the number of keys, and the unlucky insert that triggers it pays the whole bill at once. But it happens rarely enough that, smeared across every insert, the cost stays flat — O(1) on average. It's the exact same amortized bargain you met with list append back in chapter 6: mostly-free operations, punctuated by an occasional pause to rebuild the world.

Sit with what that threshold implies: a dict is deliberately kept at least one-third empty, forever. The vacancy isn't slack it hasn't gotten around to using. It's the running room that keeps collisions rare and probes short. And it's why the dict is the heaviest container Python ships. On the machine I'm writing this on, building a one-million-entry dict reserves about 70 MiB — close to double the ~39 MiB a plain list of the very same numbers needs. Look at the bucket table alone, ignoring the numbers themselves, and it's 40.0 MiB against the list's 7.6 MiB pointer array, over five times heavier. A dict buys its speed with memory, and pays sticker price.

import sys

d = {}
print(sys.getsizeof(d))          # 64  — empty, no bucket table allocated yet
for i in range(6):
    d[i] = i
print(sys.getsizeof(d))          # 352 — the 6th key forced an 8→16 slot table

# same keys keep arrival order — a side effect of the compact table (3.7+)
plist = {}
plist["Titanium"]        = 245
plist["Blinding Lights"] = 200
plist["Levels"]          = 203
print(list(plist))            # ['Titanium', 'Blinding Lights', 'Levels']

print(hash(200))              # 200            — an int hashes to itself, every run
print(hash("Levels"))         # a huge int that DIFFERS every run — strings are salted

Step back and the whole apparatus — the buckets, the load factor, the doubling, the re-hash — rests on a single unspoken promise: hash(key) must give the same answer at lookup time that it gave when the key was inserted. Move a key to a new bucket during a resize and later come back for it, and the only way to find it again is for its hash to be exactly what it was before. Break that promise and the key is simply lost in the table — present, but unfindable.

So the real question isn't how the table works — it's what kind of object can honestly make that promise. Why can a string or a number be a key, but a list never can? →

05Why a list can't be a key

Every entry in a dict is filed by its key — but not by the key you see on the page. Python files it by the key's hash: a single number crunched out of the key's contents, and that number chooses a bucket. File this pair here. Now picture a key that can change its mind after you file it. You store ["Levels", "Avicii"] → 200; Python hashes the list, gets bucket 3, and drops the entry on that shelf. Later you rename a word inside the list. Its contents changed, so its hash changes with them. The next time you reach for it, Python hashes the new contents, computes bucket 6, opens an empty shelf, and swears the key was never there.

The 200 hasn't gone anywhere. It's still sitting in bucket 3. It has simply become unfindable — filed under an address that no longer exists. That is the quiet catastrophe Python refuses to allow: not lost data, but orphaned data, present and unreachable in the same breath.

So Python bans the failure mode before it can start. A dict key must be hashable: its hash must stay fixed for the object's entire life. For the built-in types that collapses to a single word — immutable (chapter 3's photographs, not its whiteboards). str, int, float, tuple, frozenset (plus bool and None) are frozen the moment they're made, so their hash can never drift, and they're welcome as keys. (A frozenset is a set welded permanently shut. You'll build both in the very next section; for now just read it as "an immutable collection," and therefore safe to file by.) list, dict and set can mutate in place, so they're turned away the instant you try. And the rule guards keys only: a value can be a list, a dict, a whole nested playlist. Values are cargo. Only keys are addresses.

# a dict key must be HASHABLE — its hash fixed for the object's whole life
lengths = { ("Blinding Lights", "The Weeknd"): 200 }   # tuple key — frozen, fine
lengths[("Blinding Lights", "The Weeknd")]              # 200 — same hash, found again

# a list can mutate, so Python refuses it the instant you try
{ ["Blinding Lights", "The Weeknd"]: 200 }
# TypeError: unhashable type: 'list'

# only KEYS are addresses — a VALUE can be anything, even a mutable list
plays = { "Blinding Lights": ["2019-11-29", "2020-03-20"] }
plays["Blinding Lights"].append("2026-07-10")          # fine — values face no rule

Below is the exact disaster the rule prevents — made visible. Pretend, just this once, that Python let a list be a key. It hashes to a bucket at insert time and the 200 is filed there. Now edit a word inside the list: its hash lands on a new bucket, and the arrow — the lookup — walks off to the wrong shelf. Slide it back to the original bucket and the two reunite. Anywhere else, the value is stranded.

class Key:                              # pretend a mutable object were an allowed key
    def __init__(self, n): self.n = n
    def __hash__(self):    return self.n   # hash comes FROM the contents
    def __eq__(self, o):  return self.n == o.n

k = Key(0)
d = { k: "Avicii", Key(1): ..., Key(2): ..., Key(4): ..., Key(5): ... }
k in d        # True  — filed in slot 0
k.n = 3       # mutate: the hash now points at slot 3
k in d        # False — slot 3 is empty; the "Avicii" is orphaned in slot 0

So a dict is really a wall of hashed buckets, each holding a key with a value riding shotgun. Rip the values out and keep only the hashed keys, and you haven't broken anything — you've built Python's other hash structure →

06A set is a dict with the values ripped out

You just built a dict: a hash table that jumps straight to a key's value in a single step. Now do something almost violent to it — grab the whole value column and rip it clean off. What's left is still a hash table, still jumping straight to a key in one hop, but the keys have nothing left to point at. They just are, or aren't, present. That stripped-down table is a set, and throwing the values away buys you two gifts you never asked for.

First, every element is automatically unique. Add "Titanium" to a set that already holds it and the newcomer hashes to the exact bucket the old one occupies, so the table shrugs and keeps one. Duplicates cannot survive, ever, without you writing a line to stop them. Second, the question a set answers fastest is membership: x in s is the same one-hop hash jump a dict lookup is — O(1), whether the set holds ten songs or ten million. Ask a list the same thing and it walks every element from the front, comparing as it goes — O(n), a scan that slows down in lockstep with your data.

One thing you surrender: order. A set has no positions, no index, no "first" element — songs[0] raises TypeError: 'set' object is not subscriptable. Iterate one and elements emerge in an order dictated by their hashes, not by when you added them. A set answers a single question superbly — is this in here? — and politely declines the rest.

That O(1)-versus-O(n) gap sounds abstract until you watch it open. Picture your whole library as N songs and ask one question: is "Titanium" in it? A list has to be ready to check all N. A set checks exactly one bucket, no matter how large N grows. Drag N and watch the two costs pull apart.

In code the whole personality of a set fits in a few lines. Notice the third "Titanium" never lands, that discard forgives a missing element while remove does not, and that frozenset makes an immutable twin:

# bare braces, no colons -> a set; the duplicate never lands
songs = {"Titanium", "Levels", "Titanium"}
print(len(songs))            # 2
print("Levels" in songs)     # True  -> one hash jump, O(1)

songs.add("Faded")
songs.discard("Ghost")       # not there? no complaint
# songs.remove("Ghost")      -> KeyError: 'Ghost'

locked = frozenset(songs)    # immutable, and therefore hashable

Because a set is pure membership, it does the algebra you once drew as overlapping circles — and it's genuinely useful. Say you and a friend each keep a set of liked songs. One operator apiece answers a real question:

mine  = {"Blinding Lights", "Titanium", "Levels", "Wake Me Up"}
yours = {"Titanium", "Levels", "Sunflower", "Faded"}

mine & yours   # {'Titanium', 'Levels'}          -> songs you both like
mine | yours   # all six titles, no repeats      -> everything, deduped
mine - yours   # {'Blinding Lights', 'Wake Me Up'} -> only in mine
mine ^ yours   # the four neither shares         -> symmetric difference

{"Titanium", "Levels"} <= mine   # True -> subset test

Each returns a brand-new set and leaves the originals alone (there's isdisjoint and the <=/>= subset tests too). This is the fastest way in the language to answer "what's shared?", "what's the total, once?", or "what's unique to one side?".

titles  = ["Blinding Lights", "Titanium", "Levels"]
seconds = [200, 245, 203]

lengths = dict(zip(titles, seconds))
# {'Blinding Lights': 200, 'Titanium': 245, 'Levels': 203}

for title, secs in lengths.items():
    print(title, "→", secs)

You now hold four containers — list, tuple, dict, set — each blazing at one job and clumsy at another. The next chapter lines them up in one ring: memory cost and Big-O side by side, the specialists (array, deque) that beat them in a pinch, and it opens with the decision map itself — five questions that pick your structure before you type a bracket. →