Hash tables: collisions need a plan
Picture
With three buckets, keys hashing to 1 must coexist. A hash is not a unique identity.
Predict
May a hash match replace an equality check?
Walk through the small example
No. Hash narrows the search to a bucket; equality preserves key identity inside collisions.
Mental model and complete Python solution
A hash is a hallway number, not a person’s identity. Several keys may enter the same hallway; the bucket still compares their actual keys.
What the function promises: Map supports set and get for hashable keys using separate chaining. This teaching version has fixed capacity and get raises KeyError on a miss.
class ChainMap:
def __init__(self, capacity=8):
if capacity <= 0: raise ValueError("Positive capacity required")
self.buckets = [[] for _ in range(capacity)]
def _bucket(self, key):
return self.buckets[hash(key) % len(self.buckets)]
def set(self, key, value):
bucket = self._bucket(key)
for entry in bucket:
if entry[0] == key:
entry[1] = value
return
bucket.append([key, value])
def get(self, key):
for stored, value in self._bucket(key):
if stored == key: return value
raise KeyError(key)
table = ChainMap(1)
table.set("a", 1); table.set("b", 2); table.set("a", 3)
assert table.get("a") == 3 and table.get("b") == 2
Work and storage: Expected O(1) operations under a well-distributed hash and controlled load; worst case O(n).
When to recognize it: Hash narrows the search to a bucket; equality preserves key identity inside collisions.
Check before applying it: Adversarial collisions can make operations linear, and mutable keys can become unfindable.
Change one rule
Use open addressing instead of chains.
See what changes
Probe alternative slots and preserve tombstones on deletion so searches do not stop too early.
Connect
dictionaries: Expose the machinery behind dictionary lookup.
invariants: Every stored key must live in the bucket chosen by current capacity.