Hashing and collisions

A hash function turns a key into an array index, which is why dictionaries find things in constant time. Two keys can hash to the same slot, and how the table handles that collision decides its real performance.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

Explain how a hash function turns a key into an index
Explain two ways a table handles a collision
Spot why a list cannot be a dict key and use a tuple instead

In practice

A few lines that show Hashing and collisions doing its job.

Python

class HashSet:
    def __init__(self, buckets=8):
        self.buckets = [[] for _ in range(buckets)]

    def add(self, key):
        bucket = self.buckets[hash(key) % len(self.buckets)]
        if key not in bucket:        # chaining: a list per slot
            bucket.append(key)

    def __contains__(self, key):
        return key in self.buckets[hash(key) % len(self.buckets)]

The common mistake

Watch for

Using a mutable object, such as a list, as a dictionary key. Its hash would change when it changes, so Python refuses with TypeError: unhashable type. Use a tuple.

What to know first

Your roadmap puts these before Hashing and collisions, unless you already know them.

Big-O notation

How it stays learned

Once a session shows you understand Hashing and collisions, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

Day 3First recall, while it is fresh
Day 7Second, a week on
Day 18Last, when it has settled

Where it leads

Topics that build on Hashing and collisions.

Next in the moduleFrequency counting →