Hash Tables & the Song Index
Tunebox gets a request: play track t48213. With 10 million tracks in a list,
finding it means checking them one by one — O(n), on every single play. A hash
table turns the id itself into the place the track is stored, so the lookup takes
the same few steps however big the library gets. Python's dict and set are hash
tables, and after arrays they're the most-used structure in this course.
Turning a key into an address
Arrays give O(1) access by position. A hash table borrows that: a hash function
turns a key into an integer, and % size folds that integer into a slot number —
a bucket. Same key, same bucket, every time, so storing and finding both go
straight there.
A good hash spreads keys evenly across the buckets. This toy one already put three of four ids in bucket 5 — and it has a worse flaw:
def toy_hash(key):
return sum(ord(ch) for ch in key)
print(toy_hash("Nova") % 8 == toy_hash("Avon") % 8)Python's built-in hash() does this properly. Strings get a hash randomised per
process — run hash("Nova") in two programs and you'll see two different numbers —
so nobody can pre-compute keys that collide. Small integers simply hash to themselves:
Collisions: two keys, one bucket
There are more possible keys than buckets, so collisions are guaranteed. The two classic fixes:
- Chaining — each bucket holds a short list of
(key, value)pairs. A collision appends to the list; a lookup walks the list in its bucket. - Open addressing — each bucket holds at most one entry. If a key's bucket is
taken, probe onward (the next bucket, say) until you find a free one. A lookup
follows the same path until it meets the key or an empty bucket. CPython's
dictandsetuse open addressing.
A complete chained hash table fits in a dozen lines:
Step through a lookup: hash to one bucket, then walk only that chain.
Load factor and resizing
The load factor is entries / buckets. With chaining it's the average chain
length — how many comparisons a lookup expects. Keep it bounded and lookups stay O(1).
So once a table passes a threshold it resizes: allocates about twice the buckets
and rehashes every key into its new home.
A resize is O(n), but — just like a list's append — it only happens after the table
has doubled its contents, so the cost spreads to amortized O(1) per insert.
entries, buckets, resizes = 0, 8, 0
for track in range(20):
entries += 1
if entries / buckets > 0.75:
buckets *= 2
resizes += 1
print(buckets, resizes)O(1) on average — and O(n) in the worst case
A lookup is: hash the key, jump to its bucket, compare against what's there. With a decent hash and a bounded load factor, "what's there" is a handful of entries — O(1) on average. (Hashing a string does take time proportional to its length; Python caches each string's hash after the first time.)
The worst case is every key landing in one bucket. The table becomes a list in
disguise and each operation is O(n). A deliberately terrible __hash__ shows it:
That's the attack string randomisation defends against: without it, someone could send Tunebox thousands of playlist names built to collide and make every request O(n²).
Hashable keys
A key's hash must never change while it's in the table — otherwise the key is filed in
one bucket and looked up in another. So only immutable values can be keys: str,
int, float, bool, None, and tuples or frozensets built from them.
plays = {}
plays[["Nova", "Glow"]] = 12
print(plays)❓ Cross-question — "Can my own class be a key?" Yes. By default objects hash by identity, so two
Track("t1")objects are different keys. To make equal-looking objects the same key, define__eq__and__hash__together over fields that never change — or use@dataclass(frozen=True), which writes both for you.
Counting, grouping and two-sum
Three patterns cover most everyday hash-table code. Counting — how many plays did each track get? The classic bug is adding to a count that doesn't exist yet:
KeyErrorThis should count each track's plays. It crashes on the very first play — read the error, then fix the update line.
Grouping — every track id by artist, in one pass. setdefault returns the list
for a key, creating an empty one the first time:
Two-sum — two tracks that exactly fill a gap, in unsorted order. For each track
the partner you need is gap − minutes, and asking a dict whether you've seen it is
O(1): one O(n) pass, no sort, O(n) memory.
Complexity at a glance
| operation | average | worst |
|---|---|---|
d[key], d[key] = v, key in d, del d[key] |
O(1) | O(n) |
s.add(x), x in s, s.discard(x) |
O(1) | O(n) |
| build from n items | O(n) | O(n²) |
| iterate over all entries | O(n) | O(n) |
| a single resize | O(n) — amortized O(1) per insert | |
| memory | O(n) | O(n) |
Coming from Java/JS:
dictisHashMap/MapandsetisHashSet/Set; Java'shashCode/equalscontract is Python's__hash__/__eq__. One JS trap doesn't exist here: a plain JS object turns every key into a string, soobj[1]andobj["1"]are the same entry. A Python dict keeps1and"1"apart.
Idioms & real-world patterns
Counter and defaultdict
The standard library has counting and grouping built in:
Sets for "have I seen this?"
A set is a hash table with keys and no values — made for dedupe and membership:
⚡ Advanced — tuples as composite keys
When a key is "more than one thing", pack it into a tuple. frozenset is the hashable
cousin of set, for when the parts have no order.
⚡ Advanced — how a dict remembers order
Since Python 3.7 a dict iterates in insertion order. Entries live in a dense array in the order they were added, and the hash table itself is a sparse array of small integers pointing into it. Lookups go through the sparse table; iteration just walks the dense array. It uses less memory than the old design and gives you ordering.
🎯 Your turn
Build the song index: build_index(tracks) takes track dicts and returns two lookups,
built in one pass:
"by_id"— each track'sid→ itstitle"by_artist"— each artist → their tracks' titles, in library order
For example, build_index([{"id": "t1", "title": "Glow", "artist": "Nova"}, {"id": "t2", "title": "Tide", "artist": "Echo"}, {"id": "t3", "title": "Ember", "artist": "Nova"}]) →
{"by_id": {"t1": "Glow", "t2": "Tide", "t3": "Ember"}, "by_artist": {"Nova": ["Glow", "Ember"], "Echo": ["Tide"]}}
Hint — start two empty dicts, loop over the tracks once, and use
setdefault(artist, []) for the grouping.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅