Day 76 — Hashing maths & collisions

Updated

July 30, 2026

Day 76 — Hashing mathematics and collisions

Stage VII · concept day
Goal: Model hash maps into \(m\) buckets; use uniformity assumptions; analyze collisions and the birthday bound \(\approx\sqrt{\pi m/2}\); relate load factor to chaining vs open addressing as math; state a simple universal hash idea.

Why this matters

Hashing is where modular arithmetic meets counting and probability. Engineers say “mod table size”; mathematicians say “map into \(\mathbb{Z}/m\mathbb{Z}\).” Collision bounds (birthday paradox lite) explain why cryptographic hash outputs need many bits and why load factors matter — as quantitative literacy, not as a coding lab.

Note

No labs / no hash-table projects. Definitions, counting arguments, worked probability, written exercises only.

Theory

Hash functions as maps

Definition (hash function, mathematical). A hash function from a universe \(U\) of keys to \(m\) buckets is a function \[ h:U\to \{0,1,\ldots,m-1\}. \] Often \(U\) is huge and \(m\) is modest (table size).

Modular hash (simple model). For integer keys and table size \(m\), \[ h(k)=k\bmod m. \] Then \(h(k)=h(k+tm)\) for every integer \(t\) — structured collisions along arithmetic progressions. Good when keys are “random-ish”; bad when keys share a common difference multiple of a factor of \(m\).

Division method literacy. Same as modular hash. Multiplication method (idea): use fractional parts of \(kA\) for irrational-ish \(A\); still lands in \(m\) buckets. We will not drill floating-point.

Collisions

Definition. A collision for \(h\) is a pair of distinct keys \(k_1\neq k_2\) with \(h(k_1)=h(k_2)\).

Pigeonhole (absolute). If \(|U|>m\), every function \(h:U\to\{0,\ldots,m-1\}\) has a collision. Perfect hashing of a static set \(S\) requires \(|S|\le m\) at minimum for injectivity into \(m\) buckets.

Load factor

If \(n\) keys are placed into \(m\) buckets, the load factor is \[ \alpha = \frac{n}{m}. \] Under idealized simple uniform hashing — each key independently uniformly random in \(\{0,\ldots,m-1\}\) — the expected number of keys in a fixed bucket is \(\alpha\).

Collision probability for one pair

Under uniform independent hashing into \(m\) buckets, for a fixed pair of distinct keys, \[ P(h(k_1)=h(k_2)) = \frac{1}{m}. \] Among \(n\) keys there are \(\binom{n}{2}\) pairs. Linearity of expectation (Day 87) gives expected number of colliding pairs \[ \mathbb{E}[X]=\binom{n}{2}\frac{1}{m}=\frac{n(n-1)}{2m}. \] This is not the probability that at least one collision occurs, but it is the right first estimate: when \(\mathbb{E}[X]\) is order \(1\), collisions become likely.

Birthday bound

Problem. Throw \(n\) balls independently uniformly into \(m\) bins. What \(n\) makes a collision probable?

Exact probability of no collision: \[ P(\text{all distinct})=\frac{m(m-1)\cdots(m-n+1)}{m^n}=\prod_{i=1}^{n-1}\Bigl(1-\frac{i}{m}\Bigr) \] for \(n\le m\).

Approximation. Using \(1-x\le e^{-x}\), \[ P(\text{no collision})\le \exp\Bigl(-\frac{n(n-1)}{2m}\Bigr). \] Thus when \(n\approx \sqrt{2m\ln 2}\), the collision probability is about \(1/2\). The classic birthday constant: for \(m=365\), \(n\approx 23\) already yields \(>50\%\) chance two share a birthday.

Asymptotic rule of thumb. Collisions become likely around \[ n \approx \sqrt{\frac{\pi m}{2}} \] for the expected waiting time form of the birthday problem (mean number of samples until first collision is asymptotic to that). For order-of-magnitude literacy: \[ n = \Theta(\sqrt{m}) \] suffices to force collisions with constant probability. Cryptographic moral: a hash with \(b\)-bit output (\(m=2^b\)) needs \(n\sim 2^{b/2}\) work for birthday collision attacks — not \(2^b\).

Chaining vs open addressing (mathematical load)

Chaining (separate chaining). Each bucket holds a list. Under simple uniform hashing, successful search cost is related to \(1+\alpha/2\) expected comparisons in standard analyses (order \(\Theta(1+\alpha)\)). Unsuccessful search \(\Theta(1+\alpha)\). Takeaway: performance degrades smoothly with \(\alpha\); \(\alpha>1\) is allowed.

Open addressing. All keys live in the table array; probe sequences find empty slots. Load factor must satisfy \(\alpha<1\). Expected probes for unsuccessful search under uniform probing idealization behave like \(1/(1-\alpha)\) — blows up as \(\alpha\to 1^-\). Takeaway: keep \(\alpha\) bounded away from \(1\) (e.g. \(0.5\)–\(0.7\) in practice — culture, not a theorem you must re-derive).

Simple universal hashing

Idea. Adversarial keys can defeat a fixed \(h\) (e.g. all keys \(\equiv r\pmod m\)). A family \(\mathcal{H}\) of hash functions is universal if for all distinct \(k_1,k_2\in U\), \[ P_{h\sim\mathcal{H}}(h(k_1)=h(k_2))\le \frac{1}{m}, \] when \(h\) is drawn uniformly from \(\mathcal{H}\).

Classic modular family (Carter–Wegman style, statement). For prime \(p\ge |U|\) and table size \(m\), functions \[ h_{a,b}(x)=((ax+b)\bmod p)\bmod m,\qquad a\in\{1,\ldots,p-1\},\; b\in\{0,\ldots,p-1\} \] form a universal (in fact strongly universal / pairwise independent) family for appropriate statements in textbooks.

Moral. Randomness in the choice of \(h\) restores the \(1/m\) collision probability even for worst-case key pairs — analysis assumes random \(h\), not random keys.

Connection to earlier days

Tool Role in hashing
\(k\bmod m\) Bucket index
Pigeonhole Inevitable collisions if \(n>m\)
\(\binom{n}{2}/m\) Expected colliding pairs
Birthday \(\sqrt{m}\) Collision threshold
Universal family Adversarial-key insurance

Worked examples

Example 1 — Modular clustering.
\(m=10\), keys \(20,30,40,50\): all hash to \(0\). Arithmetic progression with difference \(10\).

Example 2 — Expected colliding pairs.
\(n=50\) keys, \(m=1000\) buckets: \(\mathbb{E}[X]=\frac{50\cdot 49}{2\cdot 1000}=1.225\). About one colliding pair expected — collisions not rare.

Example 3 — Birthday half-probability.
Solve \(n(n-1)/(2m)\approx \ln 2\) ≈ \(0.693\). For \(m=365\): \(n(n-1)\approx 506\), \(n\approx 23\).

Example 4 — Crypto bit length.
For \(m=2^{128}\), birthday at \(\sim 2^{64}\) hashes. “128-bit security against collision” needs roughly \(256\)-bit output in naive birthday terms for collision resistance goals — literacy only.

Example 5 — Load factor chaining.
\(n=300\), \(m=100\), \(\alpha=3\). Expected chain length \(3\). Search is \(O(1+\alpha)\) under ideal assumptions — here order \(4\), not order \(n\).

Example 6 — Open address blow-up.
Ideal unsuccessful probes \(\approx 1/(1-\alpha)\): \(\alpha=0.5\) → \(2\); \(\alpha=0.9\) → \(10\); \(\alpha=0.99\) → \(100\).

Example 7 — Pigeonhole.
\(|U|=10^6\), \(m=10^3\): every \(h\) has collisions. Minimum max-bucket load \(\ge\lceil n/m\rceil\) when placing \(n\) keys (always).

Example 8 — Probability all distinct.
\(m=5\), \(n=3\): \(P=\frac{5\cdot 4\cdot 3}{5^3}=\frac{60}{125}=0.48\). Collision probability \(0.52\).

Example 9 — Universal idea.
Fixed \(h(k)=k\bmod 8\) fails on even keys all mapping into even buckets if structure aligns. Drawing \(h_{a,b}\) randomly makes any fixed pair collide with probability \(\le 1/m\).

Example 10 — Expected empty buckets.
Under uniform independent placement of \(n\) keys in \(m\) buckets, \(P(\text{bucket }i\text{ empty})=(1-1/m)^n\approx e^{-\alpha}\). Expected empty count \(m e^{-\alpha}\) approximately.

Exercises

A. Models and pigeonhole

  1. Define collision and load factor formally.
  2. Why does \(h(k)=k\bmod m\) send \(k\) and \(k+m\) to the same bucket?
  3. Prove: if \(n>m\), some bucket has at least two of \(n\) keys (any \(h\)).
  4. If \(n\) keys go into \(m\) buckets, prove some bucket has at least \(\lceil n/m\rceil\) keys.
  5. Give keys that all collide under \(h(k)=k\bmod 16\) but not under \(h(k)=k\bmod 15\).

B. Pair collisions and expectation

  1. For \(n=100\), \(m=10^4\), compute \(\mathbb{E}[X]\) for number of colliding pairs under uniform independent hashing.
  2. For what \(n\) (approx) is \(\mathbb{E}[X]=1\) when \(m=10^6\)?
  3. Explain the difference between \(\mathbb{E}[X]\ge 1\) and \(P(X\ge 1)\ge 1/2\).
  4. Compute exact \(P(\text{collision})\) for \(n=3\), \(m=10\).
  5. Using \(1-x\le e^{-x}\), show \(P(\text{no collision})\le e^{-n(n-1)/(2m)}\).

C. Birthday bound

  1. Estimate \(n\) for \(50\%\) collision chance with \(m=365\) (show calculation).
  2. Estimate \(n\) for \(m=2^{32}\) (32-bit hash) at constant collision probability.
  3. Explain in prose why collision resistance needs roughly twice the bits of preimage folklore targets (birthday).
  4. Birthdays: if years had \(m=1000\) days, about how many people for \(\sim 50\%\) shared day?

D. Load factor and table math

  1. Chaining: \(m=1000\), \(n=3000\). What is \(\alpha\)? Expected keys per bucket?
  2. Open addressing: why is \(\alpha=1.2\) impossible for a full table of size \(m\)?
  3. Compare expected unsuccessful probes \(1/(1-\alpha)\) at \(\alpha=0.5\) vs \(0.8\).
  4. If rehashing doubles \(m\) when \(\alpha>\frac{3}{4}\), describe the load just before and after a rehash starting from \(m=16\), keys inserted one-by-one until first rehash (count).
  5. Expected empty buckets approx \(m e^{-n/m}\) for \(n=m\): numerical value of fraction empty.

E. Universal hashing and literacy

  1. State the definition of a universal hash family.
  2. Why does a fixed public \(h\) fail against adversarial keys?
  3. CS literacy: separate chaining vs open addressing — two mathematical bullets each (no code).
  4. If cryptographic hash output is \(b\) bits, birthday collision work is order \(2^{b/2}\). Compute for \(b=160\) and \(b=256\).
  5. Stretch: prove that for any fixed distinct \(k_1,k_2\), a uniformly random function \(h:U\to[m]\) satisfies \(P(h(k_1)=h(k_2))=1/m\).
  6. Stretch: show \(\sum_{i=0}^{n-1} i = n(n-1)/2\) appears naturally in the exponent of the birthday product approximation.

Deep dive — birthday approximation derivation

Start from \[ \ln P(\text{no collision})=\sum_{i=1}^{n-1}\ln\Bigl(1-\frac{i}{m}\Bigr). \] For small \(x\), \(\ln(1-x)\approx -x-x^2/2-\cdots\). Leading term: \[ \sum_{i=1}^{n-1}\frac{i}{m}\approx \frac{n^2}{2m}. \] Hence \(P(\text{no collision})\approx e^{-n^2/(2m)}\). Set equal to \(1/2\): \(n^2/(2m)\approx\ln 2\), so \(n\approx\sqrt{2m\ln 2}\approx 1.177\sqrt{m}\).
The mean waiting time until first collision is asymptotic to \(\sqrt{\pi m/2}\approx 1.25\sqrt{m}\). Both are \(\Theta(\sqrt{m})\).

Deep dive — chaining cost model (math only)

Under simple uniform hashing, bucket load \(X\sim\mathrm{Bin}(n,1/m)\) approximately, \(\mathbb{E}[X]=\alpha\).
Successful search cost is often modeled as \(1+\Theta(\alpha)\) comparisons depending on list implementation details — the shape is linear in \(\alpha\), not in \(n\) alone. That is why tables grow with \(n\) (rehash to keep \(\alpha\) bounded).

Open addressing: probe sequences; clustering analysis is deeper; the \(1/(1-\alpha)\) formula is the ideal uniform probing heuristic from textbooks.

Additional worked examples

Example 11 — Expected colliding pairs table.

\(n\) \(m\) \(\mathbb{E}[X]=\binom{n}{2}/m\)
10 100 0.45
50 100 12.25
100 365 ≈ 13.6
23 365 ≈ 0.69

Example 12 — Max load lower bound.
Always some bucket \(\ge\lceil n/m\rceil\). For \(n=m\), some bucket \(\ge 1\) (trivial); with high probability max load is \(\Theta(\log n/\log\log n)\) for balls-and-bins — awareness, not required proof.

Example 13 — Structured keys.
Keys \(0,256,512,768\) with \(m=256\): all map to \(0\) under \(k\bmod 256\). Universal family randomizes the multiplier to break this.

Example 14 — Crypto hash length.
Output \(64\) bits: birthday at \(\sim 2^{32}\) — often too low for collision resistance goals. Output \(256\) bits: birthday \(\sim 2^{128}\).

Example 15 — Load after rehash.
\(m=16\), insert until \(\alpha>0.75\) ⇒ at \(n=13\) rehash to \(m=32\), new \(\alpha=13/32\approx 0.41\).

More exercises

  1. Derive \(n\approx\sqrt{2m\ln 2}\) from \(e^{-n^2/(2m)}=1/2\).
  2. For \(m=2^{20}\), estimate \(n\) for \(50\%\) collision probability.
  3. Compare \(\mathbb{E}[X]\) and union bound \(P(\text{collision})\le\mathbb{E}[X]\).
  4. If each of \(n\) keys independently hashes uniform, expected number of nonempty buckets is \(m(1-(1-1/m)^n)\). Expand for small \(\alpha\).
  5. CS: why power-of-two table sizes interact badly with low-bit structure of some keys.
  6. Prove that a random function collides a fixed pair with prob \(1/m\).
  7. Open addressing: plot (by hand, few points) \(1/(1-\alpha)\) for \(\alpha=0.1,0.5,0.8,0.9\).

Selected mini-solutions

  1. \(\binom{100}{2}/10^4=4950/10000=0.495\).
  2. \(n(n-1)/(2m)\approx 1\) ⇒ \(n\approx\sqrt{2m}\).
  3. \(n(n-1)\approx 2\cdot 365\cdot 0.693\approx 506\) ⇒ \(n\approx 23\).
  4. \(\alpha=3\), expected chain length \(3\).

Common pitfalls

Pitfall Fix
Thinking good hash ⇒ no collisions Pigeonhole forbids when \(n>m\)
Using \(n=m\) as “safe” Birthday collisions much earlier at \(\sqrt{m}\)
Confusing expected pair-collisions with \(P(\ge 1\) collision\()\) Related but not equal
Open addressing with \(\alpha>1\) Impossible for distinct keys in array of size \(m\)
Assuming keys are random when adversary chooses them Need universal / keyed hashing story
Confusing \(2^{b}\) preimage work with \(2^{b/2}\) collision work Birthday

Study notes — hashing quantities

Quantity Formula / scale
Load \(\alpha\) \(n/m\)
Pair collision prob \(1/m\) (uniform model)
\(\mathbb{E}[\#\) colliding pairs\(]\) \(\binom{n}{2}/m\)
Birthday threshold \(\Theta(\sqrt{m})\), \(\sim\sqrt{\pi m/2}\) mean wait
Chaining search \(\Theta(1+\alpha)\) shape
Open address fail probes \(\sim 1/(1-\alpha)\) ideal
Universal \(P(h(k_1)=h(k_2))\le 1/m\)

Synthesis — hashing maths workout

S1. Prove pigeonhole: \(n>m\) keys ⇒ some bucket has \(\ge 2\) keys for any \(h\).

S2. Compute \(\mathbb{E}[\text{colliding pairs}]\) for \(n=40\), \(m=500\).

S3. Estimate \(n\) for \(50\%\) collision chance when \(m=10^6\) using \(\sqrt{2m\ln 2}\).

S4. Chaining: \(\alpha=2.5\) — what does expected bucket load mean operationally?

S5. Open addressing: evaluate \(1/(1-\alpha)\) at \(\alpha=0.5,0.75,0.9\).

S6. State universal hashing definition; give one sentence why fixed \(k\bmod m\) fails adversaries.

S7. Crypto: birthday work for \(b=128\) and \(b=256\) bit outputs.

S8. Expected empty buckets approx \(m e^{-n/m}\) at \(n=m\): numerical fraction empty.

Checkpoint

  • Can define hash, collision, load factor
  • Can compute \(\mathbb{E}[\text{colliding pairs}]\)
  • Can state birthday bound \(\sim\sqrt{m}\) and \(\sqrt{\pi m/2}\) literacy
  • Can compare chaining vs open addressing via \(\alpha\)
  • Can state universal hashing idea
  • Exercises A–D done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — expected colliding pairs vs collision probability

Let \(X=\sum_{1\le i<j\le n} I_{ij}\) where \(I_{ij}=1\) if keys \(i,j\) collide under uniform independent hashing into \(m\) buckets. Then \(\mathbb{E}[I_{ij}]=1/m\) and by linearity \[ \mathbb{E}[X]=\binom{n}{2}\frac{1}{m}. \] Markov: \(P(X\ge 1)\le\mathbb{E}[X]\). So when \(\mathbb{E}[X]\) is small, collision probability is small. When \(\mathbb{E}[X]\gg 1\), Markov does not force \(P(X\ge 1)\) near \(1\) by itself, but the birthday product approximation does: \(P(\text{no collision})\approx e^{-n(n-1)/(2m)}\).

Moral. Use \(\mathbb{E}[X]\) as a first calculator; use the exponential approximation for the \(50\%\) threshold; use pigeonhole for the absolute \(n>m\) guarantee.

Deeper theory — why universal hashing beats fixed modular hash

Adversarial pattern. If \(h(k)=k\bmod m\) is public and fixed, an adversary feeds keys \(k,k+m,k+2m,\ldots\) — all collide in one bucket. Load becomes \(\Theta(n)\) in that bucket.

Universal family. Drawing \(h\) at random from a universal family ensures that for every fixed pair, \(P(h(k_1)=h(k_2))\le 1/m\), even if the adversary chose the pair knowing the family (but not the random draw). Expected colliding pairs remains \(\le\binom{n}{2}/m\).

Pairwise independence literacy. Strongly universal families make \((h(k_1),h(k_2))\) uniform on \([m]^2\) for \(k_1\neq k_2\) — stronger than universal; the modular \(((ax+b)\bmod p)\bmod m\) family is the standard textbook construction.

Worked examples — numbers you can trust

Example 16 — Birthday for \(m=2^{16}\).
\(n\approx\sqrt{2\cdot 2^{16}\ln 2}\approx\sqrt{2^{17}\cdot 0.693}\approx\sqrt{90800}\approx 301\). About \(300\) random \(16\)-bit hashes already collide with probability \(\sim 1/2\).

Example 17 — Expected pairs table extension.
\(n=100\), \(m=500\): \(\mathbb{E}[X]=4950/500=9.9\) — expect about ten colliding pairs; many collisions almost sure.

Example 18 — Empty buckets at \(\alpha=1\).
\(m e^{-1}\approx 0.37m\) empty expected under independent uniform model — about \(37\%\) empty, so some buckets have more than one key even when \(n=m\).

Example 19 — Open addressing at \(\alpha=0.7\).
Ideal unsuccessful probes \(\approx 1/(1-0.7)\approx 3.33\). At \(\alpha=0.95\): \(\approx 20\). Rehash before the blow-up.

Extra exercises — hashing maths

  1. Derive \(P(\text{no collision})=\prod_{i=1}^{n-1}(1-i/m)\) carefully (ordered insertion).
  2. For \(m=10^9\), estimate \(n\) with \(\mathbb{E}[X]=1\).
  3. Prove: under uniform independent hashing, expected max load is at least \(\lceil n/m\rceil\) (trivial lower bound) — and state the \(\Theta(\log n/\log\log n)\) high-probability culture bound for \(n=m\).
  4. Universal: why does \(h_{a,b}\) need \(a\not\equiv 0\pmod p\)?
  5. Crypto: birthday work for \(b=80\) bit tags (short MACs) — order of magnitude.
  6. Chaining: if \(\alpha=4\), expected successful search shape \(\Theta(1+\alpha)\) — numerical order.
  7. Show union bound \(P(\text{collision})\le\binom{n}{2}/m\) and compare to \(1-e^{-n(n-1)/(2m)}\).
  8. CS prose: power-of-two \(m\) with keys sharing low bits — what goes wrong with \(k\bmod m\)?

Mini-solutions (selected)

  1. \(n(n-1)/(2\cdot 10^9)\approx 1\) ⇒ \(n\approx\sqrt{2\cdot 10^9}\approx 44721\).
  2. \(2^{40}\) order birthday work.
  3. Union bound is linear in \(\binom{n}{2}/m\); exponential approx is tighter near the transition.

Closing synthesis card

Quantity Own it?
\(\alpha=n/m\) □
\(\mathbb{E}[\text{pairs}]=\binom{n}{2}/m\) □
Birthday \(\Theta(\sqrt{m})\) □
Chaining vs open address via \(\alpha\) □
Universal definition □

Tomorrow

Day 77 — Diffie–Hellman and RSA mathematical stories.