cconnected.
Understand the pattern. Find your own way.Find your starting point
Your learning feed/Idea 36 of 218
Ideas this builds on
Arrays, search & sorting36 / 218

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.