When two keys share a bucket
Lesson 6-1 ended with ben and cai both hashing to bucket 3. That is a collision, and with more keys than buckets, collisions are mathematically unavoidable (six keys cannot spread over four buckets one-each: the pigeonhole principle).
The standard fix is chaining: each bucket holds a small list of key-value pairs instead of a single pair. Operations become:
- put(key, value): hash to a bucket, scan its little list. Key already there: overwrite. Otherwise append the pair.
- get(key): hash to a bucket, scan its little list for the key.
The magic of O(1) survives as long as chains stay short. With n keys spread over n buckets by a good hash function, the average chain holds about 1 pair, so the scan is a step or two.
Code exercise · python
Run this. Six names drop into 4 buckets, so collisions are guaranteed. Chaining just lets bucket-mates share: no chain here is longer than 2.
Code exercise · python
Your turn: finish the HashTable class. `put` must overwrite the value if the key already exists in its bucket, else append `[key, value]`. `get` returns the value or None. The `_index` helper (the hash) is written for you.
Load factor: the dynamic array trick again
What if you cram 1,000 keys into 8 buckets? Chains average 125 pairs, and every get scans a chain: lookups slide toward O(n). The table's fullness, keys ÷ buckets, is called the load factor.
Real hash tables watch it. When the load factor passes a threshold (CPython's dict resizes around ⅔), the table allocates a bigger bucket array and re-hashes every key into it (bucket = hash % n changes when n changes, so everything moves).
Sound familiar? It is lesson 2-2's growth strategy: a rare O(n) rebuild paid for by growing multiplicatively, keeping put and get amortized O(1). Two structures, one idea: buy cheap operations with occasional planned rebuilds.
Quiz
A hash table has 1,000,000 keys but only 10 buckets. What have its lookups become?