Capstone: Quarry's Hash Kernel

In short: Every earlier lesson in this section built one piece of arithmetic. The hash kernel puts them to work together: it folds real strings into numbers, picks a modulus that won't cluster them, and tells you whether the collisions it's seeing are bad luck or a bad choice of modulus.

What you're building

hash_kernel_report(strings, base, mod) -> {
    "hashes": [...],
    "collisions": int,
    "buckets_used": int,
    "is_prime_mod": bool,
    "expected_collisions": float,
}

hash_kernel_report(["cat", "dog", "bird", "cat"], 131, 97)
# {"hashes": [3, 70, 51, 3], "collisions": 1, "buckets_used": 3,
#  "is_prime_mod": True, "expected_collisions": 0.0619}

hashes: poly_hash(s, base, mod) for every string, in order — lesson 2's running total, modded every step.
collisions: how many pairs of strings landed on the same hash. "cat" appears twice, so it collides with itself once — that's not the modulus's fault, it's the same string twice, and a real system would need to compare the actual strings, not just their hashes, before trusting a match.
buckets_used: how many distinct hash values came out — the same "does capacity resist clustering" question from lesson 1, now measured instead of assumed.
is_prime_mod: lesson 1's is_prime, checking whether mod itself is a sound choice.
expected_collisions: the birthday bound — lesson 3's combinatorics, turned into a sanity check: for n strings landing uniformly at random across mod buckets, about how many colliding pairs should you expect by chance alone?

Why the birthday bound, and not "n divided by mod"

With 23 people in a room, the odds two share a birthday are better than even — far more than 23 / 365 suggests, because it's not "does any one pair match", it's "does any of the C(23, 2) = 253 pairs match". The same counting applies to hashes: with n strings and mod buckets, the number of pairs is C(n, 2) = n·(n-1)/2, and each pair collides with roughly 1/mod probability, so the expected number of colliding pairs is close to:

python

A measured collision count far above this estimate means something is wrong with the hash or the modulus — not just bad luck. A prime modulus keeps the hash's arithmetic from lining up with any structure in the input (lesson 1's "why prime bucket counts resist clustering," applied to a modulus instead of a table size); a power-of-two modulus is exactly the case that goes wrong, because it only keeps the low bits of the hash.

step through it

1import random

2random.seed(7)

4def poly_hash(s, base, mod):

5 h = 0

6 for ch in s:

7 h = (h * base + ord(ch)) % mod

8 return h

10def measured_collisions(n, mod, base=131):

11 words = ["".join(random.choices("abcdefgh", k=6)) for _ in range(n)]

12 hashes = [poly_hash(w, base, mod) for w in words]

13 seen = {}

14 for h in hashes:

15 seen[h] = seen.get(h, 0) + 1

16 return sum(c * (c - 1) // 2 for c in seen.values() if c > 1)

18for n in (50, 100, 200, 400):

19 prime_mod = 97

20 pow2_mod = 64

21 expected = n * (n - 1) / (2 * prime_mod)

22 print(n, "prime mod:", measured_collisions(n, prime_mod),

23 "pow2 mod:", measured_collisions(n, pow2_mod),

24 "birthday estimate:", round(expected, 1))

Run it and watch the power-of-two column pull away from the birthday curve far faster than the prime column does — the strings here only use 8 distinct letters, and a power-of-two modulus is far more sensitive to that kind of narrow alphabet than a prime one is.

Putting the report together

python

What it costs

piece	cost	from
`poly_hash` per string of length k	O(k)	lesson 2
`is_prime` on the modulus	O(√mod)	lesson 1
counting collisions over n hashes	O(n) with a dict	—
birthday estimate	O(1)	lesson 3
whole report over n strings, average length k	O(n·k + √mod)	all three combined

Quick practice

What does this print?

def birthday_estimate(n, mod):
    return n * (n - 1) / (2 * mod)

print(birthday_estimate(10, 45))

What does this print?

from collections import Counter

hashes = [3, 70, 3, 3, 51]
print(sum(c * (c - 1) // 2 for c in Counter(hashes).values()))

🎯 Your turn

Build hash_kernel_report(strings, base, mod): fold every string with poly_hash, then report the hashes, how many pairs collided, how many distinct buckets were used, whether mod is prime, and the birthday-bound estimate of expected collisions — rounded to 4 decimal places.

hash_kernel_report(["cat", "dog", "bird", "cat"], 131, 97) → {"hashes": [3, 70, 51, 3], "collisions": 1, "buckets_used": 3, "is_prime_mod": True, "expected_collisions": 0.0619}
hash_kernel_report(["a", "b", "c"], 131, 1000000007) → {"hashes": [97, 98, 99], "collisions": 0, "buckets_used": 3, "is_prime_mod": True, "expected_collisions": 0.0}

Hint: reuse poly_hash for the list of hashes, a dict to count repeats for collisions and buckets_used, is_prime from lesson 1 on mod, and n * (n-1) / (2 * mod) rounded to 4 places for expected_collisions.

Press ▶ Run, then ✓ Check. That closes Quarry's hash kernel: every piece from this section, working on real strings.

Capstone — Quarry's Hash Kernel