AI Hints
DSA in Python · Lesson 20 of 132

Collisions

When two keys share a bucket.

⏱ 2 min read▶ Video at 23:08🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Collisions
From the video: Collisions
  • 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.

hashtable.pypython
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"))
Output
[]
[['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.

keyvalue
Collisiontwo keys, one bucket
Chaininga small list per bucket
Resizegrow when two thirds full
AverageO(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)
Next up: Dictionaries in Practice — get, Counter, defaultdict