Collisions
When two keys share a bucket.
With millions of keys and a limited number of buckets, two keys will sometimes land in the same bucket. That's called a collision. Every hash table needs a plan for it.

- Two keys, one bucket
- A collision
- Every hash table has a plan
A tiny hash table
Let's build our own hash table, to see collisions. Each bucket is a list of key value pairs. Put adds a pair to the right bucket, or updates it if the key is already there. Get looks only in that one bucket. We use just four buckets, so collisions are guaranteed. Run it. One bucket holds three names, but get still finds every key.
class HashTable:
def __init__(self, size=4):
self.buckets = [[] for _ in range(size)]
def _bucket(self, key):
return self.buckets[sum(map(ord, key)) % len(self.buckets)]
def put(self, key, value):
b = self._bucket(key)
for pair in b:
if pair[0] == key:
pair[1] = value; return
b.append([key, value])
def get(self, key):
for k, v in self._bucket(key):
if k == key: return v
t = HashTable()
for name, age in [("Priya", 31), ("Sam", 25), ("Alex", 40), ("Jo", 22), ("Mia", 35)]:
t.put(name, age)
print(*t.buckets, sep="\n")
print("Jo is", t.get("Jo"))[] [['Priya', 31], ['Sam', 25], ['Jo', 22]] [['Alex', 40]] [['Mia', 35]] Jo is 22
Keeping it fast
If buckets get crowded, lookups slow down, because each bucket must be searched. So real hash tables grow. When they get about two thirds full, Python makes a bigger table, and moves every key across. That keeps buckets short, and lookups O of one on average. In the very worst case, with terrible luck, it's O of N.
| key | value |
|---|---|
| Collision | two keys, one bucket |
| Chaining | a small list per bucket |
| Resize | grow when two thirds full |
| Average | O(1); worst O(n) |
Summary
Collisions happen when keys share a bucket. Short buckets, and resizing, keep lookups O of one on average. Next, using Python's dict like a pro.
Key takeaways- Collisions are normal
- Resize keeps it fast
- Average O(1)