The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Hash Functions and Collision Resolution

Next ►
►

The NaiveHashTable from the previous lesson gave us O(1)... and lost task 3 the moment id 11 landed in its bucket. This lesson heals that wound on two fronts. First, the preventive front: understanding what makes a hash function good, because a well-designed function spreads the keys out and makes collisions rare. Second, the curative front: accepting that rare doesn't mean impossible (we'll prove it), and building a table that resolves them without losing a single piece of data. The result will be the course's definitive HashTable — with chaining, load factor and resizing — the piece TaskFlow needed for its id→task index to be trustworthy. It is the most "engineering workshop" lesson of the module: here you see how a professional data structure is really designed.

Contents

  1. What we ask of a hash function
  2. Hashing integers and hashing strings: a bad one and a good one
  3. Measuring the difference: the histogram
  4. Collisions are inevitable: the pigeonhole principle
  5. Curative strategy 1: chaining
  6. The complete HashTable class
  7. Load factor and resizing (rehashing)
  8. Curative strategy 2: open addressing
  9. Chaining vs. open addressing
  10. The O(n) worst case, properly explained

What we ask of a hash function

A hash function h(key) → integer is fit for a table if it satisfies three properties, in order of importance:

  1. Deterministic: the same key produces always the same hash (within the same run). Non-negotiable: storing and looking up use the same computation, so if h changed its mind, we would store in one bucket and search in another. A hash function that uses random or the current time is not a hash function: it's a lost-data generator.
  2. Uniform: the hashes must spread across the whole range as if they were random, without being so. If the function favors certain zones, keys pile up in a few buckets and the O(1) average erodes toward O(n). This is the hard property, and the one that separates a good function from a bad one.
  3. Fast: it runs on every put, get, delete and contains. An expensive hash function taxes every table operation; O(length of the key) is the standard.

There is a curious aesthetic tension: we want a result that looks chaotic (uniformity) produced by a totally predictable process (determinism). Designing good hash functions is the art of manufacturing reproducible chaos.

Hashing integers and hashing strings: a bad one and a good one

Integers: the easy case. hash(n) == n for small integers in Python, and it usually suffices: TaskFlow's ids (1, 2, 3...) spread perfectly with % capacity. Uniformity is inherited from the keys themselves — with the fine print that keys with a pattern (all ids multiples of 8, say) can resonate badly with certain capacities; we'll return to this in the tips.

Strings: here we have to work. A string is a sequence of characters, and each character has an integer code (ord("a") is 97). The immediate temptation is to add them up:

def sum_hash(text):
    """BAD hash function: adds up the character codes."""
    return sum(ord(c) for c in text)

It is deterministic and fast... but fatally non-uniform, due to a structural defect: addition ignores order. sum_hash("listen") and sum_hash("silent") are identical — all permutations of the same letters collide always, with any capacity. And there is a second, subtler defect: keys of similar length produce similar sums, crammed into a narrow band of values.

The classic solution is the polynomial hash: walk the characters accumulating, but multiplying the accumulator by a constant at each step, so that position matters:

def poly_hash(text, base=31):
    """Reasonable hash function: polynomial. h = c0·31^(n-1) + c1·31^(n-2) + ... + cn"""
    h = 0
    for c in text:
        h = (h * base + ord(c)) % (2 ** 32)   # cap it at 32 bits
    return h

Let's unpack why it works:

  • Each character ends up multiplied by a different power of 31 according to its position: the first character weighs 31^(n-1), the last weighs 1. Reordering the characters changes the result — goodbye to the anagram problem.
  • The repeated multiplication makes a change in a single character propagate and alter the result in an apparently chaotic way (the "reproducible chaos" we were after). Prime bases like 31 or 131 are chosen because they mix well and share no factors with common capacities.
  • The % (2 ** 32) keeps the number within 32 bits so it doesn't grow without bound; it's a containment detail, not a design one.

This scheme is not an academic toy: Java's string hash is exactly a polynomial with base 31. CPython uses something more armored (SipHash, with the between-runs randomization we saw in 05-01), but the underlying idea — mixing position and value — is the same.

Measuring the difference: the histogram

The words "uniform" and "crammed" are best understood by seeing them. Let's take 100 keys with realistic structure — the textual ids "T-001" through "T-100" of TaskFlow's tasks — and spread them over 20 buckets with each function, counting how many land in each:

keys = [f"T-{i:03d}" for i in range(1, 101)]       # T-001 .. T-100
CAPACITY = 20

def histogram(hash_function, name):
    buckets = [0] * CAPACITY
    for key in keys:
        buckets[hash_function(key) % CAPACITY] += 1
    print(f"--- {name} ---")
    for i, n in enumerate(buckets):
        print(f"{i:2} | {'#' * n} ({n})")

histogram(sum_hash, "sum_hash")
histogram(poly_hash, "poly_hash")

Output (trimmed to the most illustrative buckets):

--- sum_hash ---
 1 | ######### (9)
 2 | ########## (10)
 3 | ######### (9)
 ...
10 | ## (2)
11 | # (1)
12 |  (0)
13 |  (0)
...
--- poly_hash ---
 3 | ##### (5)
 4 | ###### (6)
 5 | ###### (6)
 6 | ##### (5)
 7 | ###### (6)
 ...

The verdict is visual: with sum_hash, the distribution is a mountain — buckets with 10 keys right next to two empty buckets (these keys' sums concentrate in a band, and the % 20 draws that band onto the table). With poly_hash, every bucket holds between 4 and 6 keys: practically the ideal of 100/20 = 5. And the anagram defect, in black and white:

print(sum_hash("T-012"), sum_hash("T-021"), sum_hash("T-102"))
# 276 276 276   ← guaranteed collision, regardless of capacity
print(poly_hash("T-012"), poly_hash("T-021"), poly_hash("T-102"))
# 78964056 78964086 78964986   ← three different values

In a table using sum_hash, searching the 10-key bucket costs twice the ideal average, and the empty buckets are wasted capacity. Uniformity is not an abstract virtue: it is running time.

Collisions are inevitable: the pigeonhole principle

What if we designed a hash function so good it never collided? Impossible, and the proof fits in two lines. The pigeonhole principle: if n pigeons are distributed among m holes and n > m, some hole holds at least two pigeons. In keys and buckets: a table of capacity 64 holding 65 keys has, with mathematical certainty, at least one collision — no matter how exquisite the function. The possible keys (all integers, all strings) always infinitely outnumber the available buckets.

And reality is even more impatient: you don't need to fill the table to collide. It's the birthday paradox: just as a room with only 23 people already has a 50% chance of two matching birthdays (with 365 "buckets"!), in a table of capacity 365 it takes only about 23 random keys for the first collision to be more likely than not. Operational conclusion: the question is never "will there be collisions?" but "what will we do when they arrive?". There are two big answers; let's start with the main one.

Curative strategy 1: chaining

Chaining dissolves the problem by changing what a bucket is: instead of room for one pair, each bucket is a container holding a collection of pairs — all the ones the hash sends there. And what structure should we use for that variable-size collection, with O(1) insertion and delete-by-predicate? We have one built and tested since module 2: the LinkedList.

graph LR
    subgraph "Bucket array (capacity 8)"
        C0["0"] --> N
        C3["3"] --> A["(3, task 3)"] --> B["(11, task 11)"] --> N3["None"]
        C5["5"] --> D["(5, task 5)"] --> N5["None"]
    end
    N["None"]

The collision from 05-01 stops being a tragedy: keys 3 and 11 share a bucket, each with its pair intact. Looking up key 3 means: compute the bucket (O(1)) and walk its small list comparing keys (O(bucket length)). If the hash function spreads well, that average length is n / capacity — a small, controlled number, as we'll see with the load factor.

The complete HashTable class

We reuse Node and LinkedList exactly as they were left in 02-02 (with insert_front, find(condition), remove(condition) and iteration). Each bucket will store pairs as [key, value] lists — mutable on purpose, so we can update the value without touching the structure:

class HashTable:
    """Key→value dictionary with chaining. The course's 'real' table."""

    MAX_LOAD_FACTOR = 0.75           # resize threshold (section 7)

    def __init__(self, capacity=8):
        self.capacity = capacity
        self.buckets = [LinkedList() for _ in range(capacity)]
        self.n = 0                   # stored pairs

    def _index(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        """Inserts or updates. Average cost: O(1)."""
        bucket = self.buckets[self._index(key)]
        pair = bucket.find(lambda p: p[0] == key)
        if pair is not None:
            pair[1] = value                  # the key existed: update
            return
        bucket.insert_front([key, value])    # new: O(1) in the list
        self.n += 1
        if self.n / self.capacity > self.MAX_LOAD_FACTOR:
            self._resize()

    def get(self, key, default=None):
        """Average cost: O(1) — one short bucket, not the whole table."""
        pair = self.buckets[self._index(key)].find(lambda p: p[0] == key)
        return pair[1] if pair is not None else default

    def contains(self, key):
        pair = self.buckets[self._index(key)].find(lambda p: p[0] == key)
        return pair is not None

    def delete(self, key):
        """Removes the pair and returns its value, or None if absent."""
        pair = self.buckets[self._index(key)].remove(lambda p: p[0] == key)
        if pair is None:
            return None
        self.n -= 1
        return pair[1]

    def __len__(self):
        return self.n

    def _resize(self):
        """Doubles the capacity and relocates ALL pairs (rehashing)."""
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [LinkedList() for _ in range(self.capacity)]
        self.n = 0
        for bucket in old_buckets:
            for key, value in bucket:        # the LinkedList's __iter__
                self.put(key, value)         # recomputed with the new capacity

Points that deserve a magnifying glass:

  • put searches first: if the key already exists, it updates the value inside the pair (pair[1] = value) and doesn't touch self.n. That honors the ADT's unique-keys contract. Only if the key is new does it insert — at the front of the bucket, which in the LinkedList is O(1).
  • Every operation repeats the same pattern: translate the key to a bucket (O(1)) and delegate to the module 2 linked list (find or remove with the predicate p[0] == key). The O(n) work those methods did over the entire list is done here over a bucket of 2 or 3 elements: same code, different world.
  • Nothing is ever lost: repeat the fatal experiment of 05-01 (put(3, t3), put(11, t11)) and you'll see get(3) and get(11) each return their own task. Bucket 3 simply holds two pairs.

Load factor and resizing (rehashing)

Chaining has a slow-moving enemy: occupancy. If we insert 800 pairs into a table of 8 buckets, each bucket ends up with ~100 — and every get walks a list of 100. Let's formalize it with the load factor:

load factor = n / capacity     (stored pairs / buckets)

It is exactly the average bucket length. At factor 0.75, the average bucket holds less than one pair; at factor 100, the table is a linked list in disguise. The defense is to watch it and, upon crossing a threshold (our MAX_LOAD_FACTOR = 0.75, similar to real-world tables), to resize: double the capacity and reinsert every pair.

Why reinsert instead of copying the buckets? Because each key's index depends on the capacity: hash(11) % 8 = 3, but hash(11) % 16 = 11. When the capacity changes, every address expires and must be recomputed — that is rehashing (you already sensed it in exercise 1 of 05-01). Two cost nuances:

  • Any single resize costs O(n): everything has to be relocated. The insertion that triggers it is, momentarily, expensive.
  • But doubling the capacity (instead of adding a bit) spaces resizes out exponentially: to reach n pairs we have paid resizes of n/2 + n/4 + n/8 + ... < n reinsertions in total. Spread over the n insertions, it comes out to O(1) amortized per insertion — the same dynamic-array argument we saw with list in 01-05. The symmetry is no accident: the hash table is an array underneath, and it inherits its tricks.

Curative strategy 2: open addressing

The second family of solutions does away with lists: everything lives inside the array itself, one pair per bucket. In open addressing, if the computed bucket is occupied by another key, the pair seeks lodging in an alternative bucket following a fixed rule. The simplest rule is linear probing: try the next bucket, and the next, advancing circularly ((i + 1) % capacity, the arithmetic of the CircularQueue from 04-03) until a free spot appears.

  • Inserting 11 when bucket 3 is occupied by key 3: probe 4; free? the pair stays there.
  • Looking up 11: compute bucket 3; there's a pair but for another key → move on to 4; key 11 → found. The search retraces the same path as the insertion and can only stop upon finding the key... or an empty bucket (if the key existed, it would have appeared before the first gap).
  • Deleting, and here comes the fine trap: if we delete key 3 leaving its bucket empty, the search for 11 will reach bucket 3, see the gap and conclude — wrongly — that 11 doesn't exist, because the gap severs the path. The standard solution is not to empty, but to leave a special marker (DELETED, a "tombstone"): the search passes through it as if occupied, the insertion may reuse it as free.

We won't implement this variant in detail (the concept is what's required here; with chaining we already have our working table), but we will cover its signature problem-idea: primary clustering. Consecutive occupied buckets form "pile-ups" that grow — every collision that lands in the pile-up lengthens it, and lengthening it makes it more likely to catch the next one. That is why open addressing is more sensitive to the load factor and usually resizes earlier (typically toward 0.5–0.7; CPython's dict, which uses a sophisticated variant of this family, resizes at 2/3).

Chaining vs. open addressing

Criterion Chaining Open addressing
Where the pairs live In lists outside the array (buckets) Inside the array itself
Collision Appended to the bucket Another bucket is probed
Deletion Simple (remove from the list) Delicate: requires DELETED markers
Tolerable load factor Can exceed 1 (buckets of several pairs) Must stay below 1, with margin
Memory Extra pointers per node Compact and friendly to the CPU cache
Signature risk Long buckets if the hash is bad Primary clustering (pile-ups)
Who uses it Java HashMap, our HashTable CPython dict/set (advanced variant)

Both families power production software; chaining is more didactic and robust under heavy loads, open addressing squeezes modern memory better. For the course, our chaining HashTable is the reference.

The O(n) worst case, properly explained

We can now settle the debt from the cost table of 05-01. The O(n) worst case happens when all the keys end up in the same bucket (or the same pile-up, in open addressing): the table degenerates into a linked list and every operation walks it in full. How does one get there?

  • A bad hash function: sum_hash with anagrammatic keys, or any function that resonates with the keys' pattern. This is the avoidable case — hence the "preventive" half of this lesson.
  • Extreme bad luck: possible, astronomically improbable with a uniform function. Probabilistic analysis says that, with a uniform hash and a bounded load factor, the average bucket holds O(1) pairs — that is why the O(1) average is a solid promise and not false advertising.
  • Bad faith: an attacker who knows the hash function can manufacture thousands of colliding keys and turn every request into O(n) (a hash flooding attack, a classic denial of service against web servers). This is why Python randomizes string hashing on every run (the note in 05-01): without knowing the seed, tailor-made collisions cannot be manufactured.

The full engineering, in one line: good hash function + watched load factor + resizing = O(1) average with the O(n) worst case confined to the improbable or the malicious.

Common Mistakes and Tips

  • Forgetting the "key already exists" case in put: appending without searching first creates duplicate keys inside the bucket; get will find one version or the other depending on order and delete will remove only one. It is the number one mistake when implementing chaining.
  • Resizing by copying buckets instead of rehashing: if you copy the lists as-is when growing, the keys sit in buckets computed with the old capacity and the table "loses" pairs (they're there, but _index no longer points at them). Every resize is a reinsertion.
  • Updating self.n at the wrong time: incrementing it when updating an existing value, or forgetting to decrement it on delete, corrupts the load factor — and with it, the resizing policy. n counts pairs, not calls.
  • In open addressing, deleting by leaving a gap: it severs the search paths of the keys that probed past it. If you ever implement it, the DELETED tombstone is not optional.
  • Ill-fitting capacities: with patterned integer keys (ids that are multiples of 4) and a power-of-two capacity, % capacity looks only at the low bits and half the table sits empty. Prime capacities (like the 13, or the 20 chosen deliberately in the examples) or a bit-mixing hash avoid the resonance. CPython solves this by mixing; our polynomial hash does too.
  • Tip: when a hash table "runs slow", print its occupancy histogram like the one in section 3. It is the X-ray that distinguishes, in seconds, a sick hash function from a runaway load factor.

Exercises

  1. Anagram diagnosis. Without running any code: which bucket will "T-123", "T-132", "T-213", "T-231", "T-312" and "T-321" land in with sum_hash and capacity 20? And does poly_hash guarantee they will not collide? Justify both answers with the properties from section 1.
  2. Linear probing on paper. Open addressing table, capacity 7, integer keys (hash(n) == n). Starting from the empty table, trace bucket by bucket: put(10), put(17), put(3), delete(10) and then contains(17). Do it twice: deleting with a gap (None) and deleting with a tombstone (DELETED). What does contains(17) answer in each case?
  3. The load factor, measured. Add to HashTable the method max_bucket_length() returning the length of the longest bucket (use len(bucket), which the LinkedList already offers). Insert the pairs (i, i) for i from 0 to 999 into two tables of initial capacity 8: a normal one and one with MAX_LOAD_FACTOR = float("inf") (resizing disabled). Compare capacity, load factor and maximum bucket of both.

Solutions

Exercise 1. The six keys are permutations of the same characters, and the sum doesn't depend on order: they all have sum_hash = ord("T") + ord("-") + ord("1") + ord("2") + ord("3") = 84 + 45 + 49 + 50 + 51 = 279, so they all land in bucket 279 % 20 = 19. Six keys, one bucket: looking up any of them costs up to 6 comparisons. With poly_hash position matters (each character is multiplied by a different power of 31), so these particular six receive different hashes — but there is no general guarantee: the pigeonhole principle still stands and poly_hash also collides for some pairs of keys. The difference is statistical, not absolute: the good function makes collisions rare and free of exploitable patterns; the bad one manufactures them in bulk.

Exercise 2. Common trace: put(10) → 10 % 7 = 3, bucket 3 free → it stays at 3. put(17) → 17 % 7 = 3, occupied (10) → probe 4, free → 4. put(3) → 3 % 7 = 3, occupied (10) → 4 occupied (17) → 5 free → 5. State: [_, _, _, 10, 17, 3, _] — a three-bucket pile-up born from a single collision: primary clustering in miniature.

  • Delete with a gap: bucket 3 becomes None. contains(17) → computes 3, sees None, answers False: key 17 sits in bucket 4, but the gap severed the path. The table just lied.
  • Delete with a tombstone: bucket 3 becomes DELETED. contains(17) → bucket 3 is a tombstone, it passes through → bucket 4, key 17 → answers True. The tombstone preserves the path; a future insertion may reuse bucket 3.

Exercise 3.

    def max_bucket_length(self):
        return max(len(bucket) for bucket in self.buckets)

normal = HashTable(capacity=8)
frozen = HashTable(capacity=8)
frozen.MAX_LOAD_FACTOR = float("inf")         # disables resizing

for i in range(1000):
    normal.put(i, i)
    frozen.put(i, i)

print(normal.capacity, len(normal) / normal.capacity,
      normal.max_bucket_length())             # 2048  0.488  1
print(frozen.capacity, len(frozen) / frozen.capacity,
      frozen.max_bucket_length())             # 8     125.0  125

The normal table kept doubling up to capacity 2048: load factor ~0.49 and buckets of at most 1 pair (consecutive integer keys: perfect distribution) — get is a single comparison. The frozen one keeps 8 buckets with 125 pairs each: every get walks up to 125 nodes. Same hash function, same keys; the only difference is the resizing policy. The O(1) average is not a gift from mathematics: it is a load factor kept in check.

Conclusion

This lesson turned the fragile idea of 05-01 into a production-grade structure. On the preventive front: a hash function must be deterministic, uniform and fast; the polynomial hash achieves uniformity by making each character's position matter, and the histogram gave us a tool to see the quality of a hash. On the curative front: the pigeonhole principle guarantees collisions, chaining resolves them by giving each bucket a LinkedList (module 2 working inside module 5), and the load factor with doubling-based resizing keeps buckets short at O(1) amortized cost — with open addressing and its tombstones as the alternative family. The result: the HashTable with put/get/delete/contains in O(1) average, its O(n) worst case explained and confined. That said: day to day you won't program your own table — Python ships two of industrial quality, dict and set, and you now know exactly what sits under their hood. The next lesson exploits them thoroughly: hashable keys, real costs, and the patterns (grouping, counting, indexing) that will make TaskFlow fly. See you in 05-03.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved