When two keys share a bucket
Lesson 6-1 ended with ben and cai both hashing to bucket 3. That is a collision, and once there are more keys than buckets it stops being bad luck and becomes arithmetic.
Six keys cannot spread one-each over four buckets, which is the pigeonhole principle. Some bucket must hold at least two.
The standard fix is chaining, where each bucket holds a small list of key-value pairs rather than a single pair. The two operations become short.
put(key, value)hashes to a bucket and scans its little list. If the key is already there, overwrite the value, otherwise append the pair.get(key)hashes to a bucket and scans its little list for the key.
The O(1) behavior survives as long as chains stay short. With n keys spread across n buckets by a decent hash function, the average chain holds about one pair, so the scan is a step or two regardless of how large n gets.
That is the honest version of the claim. A hash table is not magically O(1), it is O(1) plus the length of one chain, and the whole engineering effort goes into keeping that length near 1.
Chaining with guaranteed collisions
Six names into four buckets, so at least two buckets must be shared.
def simple_hash(key, buckets): total = 0 for ch in key: total = total * 31 + ord(ch) return total % buckets buckets = 4 names = ["ana", "ben", "cai", "dee", "eli", "fay"] table = [[] for _ in range(buckets)] for name in names: table[simple_hash(name, buckets)].append(name) for i, bucket in enumerate(table): print(i, bucket)
Output
0 ['ana', 'dee'] 1 [] 2 ['eli', 'fay'] 3 ['ben', 'cai']
[[] for _ in range(buckets)] builds a separate empty list per bucket, and it has to be a comprehension. Writing [[]] * 4 would create four references to the same list, so every append would appear in all four buckets.
Collisions did not break anything. Bucket-mates simply share their slot, and no chain here is longer than two, so a lookup scans at most two pairs.
Bucket 1 came out empty, which is normal. Hash functions scatter keys rather than distribute them evenly, so some slots stay unused while others hold two, even when the counts would allow a perfect spread.
A working hash table
_index is the hash, put overwrites or appends, and get scans the chain.
class HashTable: def __init__(self, buckets=8): self.buckets = [[] for _ in range(buckets)] def _index(self, key): total = 0 for ch in key: total = total * 31 + ord(ch) return total % len(self.buckets) def put(self, key, value): bucket = self.buckets[self._index(key)] for pair in bucket: if pair[0] == key: pair[1] = value return bucket.append([key, value]) def get(self, key): bucket = self.buckets[self._index(key)] for pair in bucket: if pair[0] == key: return pair[1] return None t = HashTable() t.put("ana", 91) t.put("ben", 84) t.put("ana", 95) print("ana:", t.get("ana")) print("ben:", t.get("ben")) print("zoe:", t.get("zoe"))
Output
ana: 95 ben: 84 zoe: None
Both methods share the same two moves, hash to a bucket then scan that bucket only. Neither ever touches another bucket, which is where the speed comes from.
The return inside put's overwrite branch is essential. Without it the loop would finish and append a second ["ana", 95] pair, leaving two entries for one key and a get that returns whichever comes first.
The third call proves the overwrite ran. t.put("ana", 95) found the existing pair and replaced its value, so the lookup reports 95 rather than the original 91.
t.get("zoe") shows the miss path. Bucket for zoe gets scanned, nothing matches, and the function falls through to return None without searching anywhere else.
Load factor: the dynamic array trick again
Cramming 1,000 keys into 8 buckets makes chains average 125 pairs, and since every get scans a chain, lookups slide toward O(n). The table's fullness, keys divided by buckets, is called the load factor.
Real hash tables watch that number. Once it passes a threshold, and CPython's dict resizes at around two thirds, the table allocates a larger bucket array and re-hashes every key into it.
The re-hashing is not optional. Because bucket = hash % n, changing n changes every key's index, so nothing can simply be copied across, exactly as lesson 6-1 showed with 8 buckets against 11.
This should look familiar, because it is lesson 2-2's growth strategy again. A rare O(n) rebuild, paid for by growing multiplicatively rather than by a fixed amount, keeps put and get amortized O(1).
Two very different structures land on one idea: buy cheap everyday operations with occasional planned rebuilds.
Lookups have become roughly O(n), since each bucket's chain holds about 100,000 pairs that have to be scanned.
Hashing to the bucket is still a single step, and that part never degrades. What degrades is the second half, because the bucket's chain is a plain list scanned front to back, which is lesson 1-1's linear search all over again.
Dividing the work by 10 does not change the growth rate either. Doubling the keys still doubles the scan, and that is the definition of linear.
O(1) lookups depend entirely on keeping chains short, which is exactly why real tables resize to hold the load factor down instead of trusting a fixed bucket count.