Module 4
Hash tables
A hash table turns “find this key” into arithmetic. Hash the key into a number, take it modulo the bucket count, and jump straight to that bucket — no scanning, no comparing against other keys. That's the whole trick behind average O(1)get, put and contains, and it's why the dict/map/HashMap is the most-used structure in working code and in interviews alike.
The honesty clauses: different keys can hash to the same bucket (collisions — inevitable with finite buckets and infinite keys), so each bucket holds a small chain that lookup must walk, comparing keys for real equality. Performance therefore depends on chains staying short, which the table maintains by resizing — when entries exceed ~75% of buckets (the load factor), it doubles the array and redistributes. Worst case, with everything colliding, lookup degrades to O(n) — the lab below lets you manufacture exactly that. And one contract matters: equal keys must hash equally, and keys must not mutate while stored, or the table looks in the wrong bucket and swears your key doesn't exist.
🎛 Bucket & collision lab
[0]
gold
[1]
copper
[2]
—
[3]
—
[4]
—
[5]
silver
[6]
—
[7]
crude
4 keys in 8 buckets — longest chain 1. Hover a key to see its hash arithmetic. Red buckets are collisions: lookup there must walk the chain and call equals on each entry. Shrink to 2 buckets and everything collides — that's the degenerate O(n) case; grow the table and chains shorten again, which is exactly what resizing at ~75% load factor does automatically.
Worked example — first non-repeating character
def first_unique(s):
counts = {} # char -> occurrences
for ch in s: # pass 1: count, O(n)
counts[ch] = counts.get(ch, 0) + 1
for i, ch in enumerate(s): # pass 2: first with count 1
if counts[ch] == 1:
return i
return -1
# Two linear passes + O(1) lookups = O(n).
# The no-hash-map version re-scans the string per character: O(n²).This “count first, decide second” shape — and its siblings “have I seen this before?” (a set) and “group these by key” (map of lists) — resolves an enormous share of problems. When an interviewer asks “can you do better than O(n²)?”, the answer is a hash map often enough that it should be your first reflex to check.
Hash map vs the alternatives
- vs sorted array + binary search: O(1) beats O(log n), but the map has no order — if the problem needs ranges, neighbors, or sorted output, sorting may serve better.
- vs set: a set is a hash map that only keeps keys — reach for it when the question is pure membership.
- Cost: O(n) extra memory and no ordering guarantees (unless you use an order-preserving variant) — name that trade when you introduce one.
Say it out loud
- “Average O(1), worst O(n) if everything collides — real implementations keep the load factor low so that doesn't happen.”
- “I'm trading O(n) memory for dropping the inner loop — n is small enough that it's a good trade.”
- “The key must be immutable while it's in the map — mutate it and it's filed in the wrong bucket.”