Hash Tables with Separate Chaining Collision Resolution
Hash tables map keys to bucket indices using `hash(k) % size`. When two keys hash to the same index (collision), separate chaining stores multiple `(key, value)` pairs in a bucket list 🗄️.
class HashMap:
def __init__(self, size=8):
self.size = size
self.buckets = [[] for _ in range(size)]
def set(self, k, v):
bucket = self.buckets[hash(k) % self.size]
for i, (existing_k, _) in enumerate(bucket):
if existing_k == k:
bucket[i] = (k, v)
return
bucket.append((k, v)) # Chaining on collision! 🗄️
def get(self, k):
bucket = self.buckets[hash(k) % self.size]
for existing_k, v in bucket:
if existing_k == k: return v
return None
m = HashMap()
m.set("alpha", 1); m.set("beta", 2)
print(m.get("alpha")) # 1 🗄️
# 15. Hash Tables with Separate Chaining Collision Resolution Hash tables map keys to bucket indices using `hash(k) % size`. When two keys hash to the same index (collision), separate chaining stores multiple `(key, value)` pairs in a bucket list 🗄️. ```python class HashMap: def __init__(self, size=8): self.size = size self.buckets = [[] for _ in range(size)] def set(self, k, v): bucket = self.buckets[hash(k) % self.size] for i, (existing_k, _) in enumerate(bucket): if existing_k == k: bucket[i] = (k, v) return bucket.append((k, v)) # Chaining on collision! 🗄️ def get(self, k): bucket = self.buckets[hash(k) % self.size] for existing_k, v in bucket: if existing_k == k: return v return None m = HashMap() m.set("alpha", 1); m.set("beta", 2) print(m.get("alpha")) # 1 🗄️ ``` Understanding collision resolution explains why Python's native `dict` is an engineering marvel: CPython uses open addressing with perturbation probing to achieve $O(1)$ speed with near-zero memory waste! 🗄️ --- ### Question How does separate chaining handle two distinct keys that produce the exact same bucket index? 🧠 - [ ] a. Appends both `(key, value)` pairs as elements inside a linked list or bucket array at that index 🗄️ - [ ] b. Overwrites and destroys the first key permanently - [ ] c. Raises a fatal `CollisionError` - [ ] d. Reboots the Python interpreter --- ### Challenge Create a minimal `HashMap` class with `set(k, v)` and `get(k)` using bucket chaining. Set `("user", "admin")`. Print `get("user")` and `get("missing")`. 🎯 <details> <summary>Solution</summary> ```python class HashMap: def __init__(self, size=4): self.size = size self.buckets = [[] for _ in range(size)] def set(self, k, v): b = self.buckets[hash(k) % self.size] for i, (ek, _) in enumerate(b): if ek == k: b[i] = (k, v) return b.append((k, v)) def get(self, k): b = self.buckets[hash(k) % self.size] for ek, v in b: if ek == k: return v return None hm = HashMap() hm.set("user", "admin") print(hm.get("user")) print(hm.get("missing")) ``` </details>