COMPX270 — Chapter 6 Supplement
Mathematical Foundations: Hashing
Modular arithmetic over finite fields, the pigeonhole principle, polynomial hash constructions, collision counting via indicator variables, load factor analysis, and Bloom filter probability derivations.
Modular Arithmetic & Finite Fields
For a positive integer \(n\), we say \(a \equiv b \pmod{n}\) if \(n\) divides \(a - b\). The set \(\mathbb{Z}_n = \{0, 1, \ldots, n-1\}\) with addition and multiplication modulo \(n\) forms a ring.
When \(p\) is prime, \(\mathbb{Z}_p\) is a field: every non-zero element has a multiplicative inverse. Specifically, for \(a \not\equiv 0 \pmod{p}\), there exists a unique \(a^{-1} \in \mathbb{Z}_p\) such that \(a \cdot a^{-1} \equiv 1 \pmod{p}\).
This follows from Fermat's Little Theorem: \(a^{p-1} \equiv 1 \pmod{p}\), so \(a^{-1} = a^{p-2} \bmod p\).
In \(\mathbb{Z}_7\): \(3^{-1} = 5\) because \(3 \times 5 = 15 \equiv 1 \pmod{7}\). Similarly, \(2^{-1} = 4\) because \(2 \times 4 = 8 \equiv 1 \pmod{7}\).
Why Primes Matter for Hashing
Universal hash families are constructed over \(\mathbb{Z}_p\) because:
- Every non-zero element has an inverse, so the linear system in the universality proof has a unique solution.
- Products and sums behave like a “nice” algebra without zero divisors.
Pigeonhole Principle
If \(n\) items are placed into \(m\) containers and \(n > m\), then at least one container holds more than one item. More generally, some container holds at least \(\lceil n/m \rceil\) items.
Application to Hashing
A hash function \(h : X \to Y\) maps a universe of size \(|X| = m\) to a table of size \(|Y| = m'\) where \(m \gg m'\). By the pigeonhole principle, there must exist distinct \(x, x' \in X\) with \(h(x) = h(x')\). In fact, for any fixed hash function, there exist at least \(\lceil m/m' \rceil\) elements mapping to the same slot.
This is why no single hash function can avoid all collisions — we need random selection from a hash family.
For any fixed \(h\), an adversary who knows \(h\) can find \(n\) elements that all collide: pick \(n\) elements from the set \(\{x \in X : h(x) = y_0\}\) for some target slot \(y_0\). By the pigeonhole principle, this set has size \(\geq m/m'\), so this attack is always possible. Randomising over \(h\) defeats the adversary.
Hash Function Constructions
For a prime \(p \geq |X|\), define \(h_{a,b}(x) = (ax + b) \bmod p\) for \(a, b \in \mathbb{Z}_p\). The family \(\mathcal{H} = \{h_{a,b}\}\) is strongly universal over \(\mathbb{Z}_p\).
Key idea: For distinct \(x \neq x'\), the pair \((h_{a,b}(x), h_{a,b}(x'))\) is uniformly distributed over \(\mathbb{Z}_p \times \mathbb{Z}_p\) as \((a,b)\) ranges over \(\mathbb{Z}_p^2\). This is because the map \((a,b) \mapsto (ax+b, ax'+b)\) is a bijection on \(\mathbb{Z}_p^2\) (the corresponding matrix has determinant \(x' - x \neq 0 \pmod{p}\)).
To map to \(\{0, \ldots, m'-1\}\), compose with a second modular reduction:
\[h_{a,b}(x) = ((ax + b) \bmod p) \bmod m'\]This is universal (Theorem 32) but generally not strongly universal, because the second \(\bmod m'\) can introduce correlations.
For higher independence, use degree-\((k-1)\) polynomials over \(\mathbb{Z}_p\):
\[h_{a_0, a_1, \ldots, a_{k-1}}(x) = \left(\sum_{i=0}^{k-1} a_i x^i\right) \bmod p\]The family over all choices of \((a_0, \ldots, a_{k-1}) \in \mathbb{Z}_p^k\) is \(k\)-independent: for any \(k\) distinct inputs, the outputs are independently and uniformly distributed over \(\mathbb{Z}_p\).
The proof uses the fact that a degree-\((k-1)\) polynomial over a field is uniquely determined by its values at \(k\) distinct points (Lagrange interpolation).
Expected Value of Collisions
Let \(S = \{x_1, \ldots, x_n\}\) be the stored elements and \(h\) a hash function from a universal family. For each pair \((i, j)\) with \(i < j\), define the indicator variable:
\[I_{ij} = \mathbf{1}[h(x_i) = h(x_j)]\]The total number of collisions is \(C = \sum_{i
By universality and linearity of expectation:
\[\mathbb{E}[C] = \sum_{iFrom Collisions to Chain Length
For a specific element \(x\), the expected chain length at slot \(h(x)\) is:
\[\mathbb{E}[\text{chain length at } h(x)] = 1 + \sum_{y \in S \setminus \{x\}} \Pr[h(y) = h(x)] \leq 1 + \frac{n-1}{m'} = 1 + \alpha\]where \(\alpha = n/m'\) is the load factor. This is the key step in proving \(O(1 + \alpha)\) expected lookup time.
Load Factor & Birthday Paradox
The load factor of a hash table is \(\alpha = n/m'\), the ratio of stored elements to table slots. It controls performance:
- Separate chaining: \(O(1 + \alpha)\) per operation.
- Open addressing: \(O(1/(1-\alpha))\) per operation (requires \(\alpha < 1\)).
- Cuckoo hashing: requires \(\alpha < 1/2\) for expected \(O(1)\) insert.
When hashing \(n\) elements into \(m'\) slots uniformly at random, the probability that all elements land in distinct slots is:
\[\prod_{i=0}^{n-1} \left(1 - \frac{i}{m'}\right) \leq \prod_{i=0}^{n-1} e^{-i/m'} = e^{-n(n-1)/(2m')}\]For this to be at most \(1/2\), we need \(n(n-1)/(2m') \geq \ln 2\), i.e., \(n \approx \sqrt{2 m' \ln 2} = \Theta(\sqrt{m'})\).
So collisions become likely when \(n = \Omega(\sqrt{m'})\). With \(m' = O(n)\), we have \(n \gg \sqrt{m'}\), so collisions are inevitable.
With \(m' = 365\) (days in a year), collisions become likely at \(n \approx \sqrt{2 \cdot 365 \cdot \ln 2} \approx 23\). This is the famous birthday paradox: in a room of 23 people, there is a \(> 50\%\) chance of a shared birthday.
For a hash table with \(m' = 1000\) slots, collisions are likely at \(n \approx 37\) elements.
Bloom Filter Probability Analysis
A Bloom filter has an array of \(m'\) bits and \(T\) independent hash functions \(h_1, \ldots, h_T\), each uniformly mapping to \(\{0, \ldots, m'-1\}\). After inserting \(n\) elements, each hash function has set \(n\) bits (with possible overlaps).
After one insertion, a specific bit remains 0 if none of the \(T\) hash functions map to it:
\[\Pr[\text{bit } i = 0 \text{ after 1 insert}] = \left(1 - \frac{1}{m'}\right)^T\]After \(n\) independent insertions:
\[\Pr[\text{bit } i = 0] = \left(1 - \frac{1}{m'}\right)^{nT} \approx e^{-nT/m'}\]using the approximation \((1 - 1/m')^{m'} \approx e^{-1}\).
A false positive occurs when all \(T\) hash bits for a non-member \(z\) are set to 1. Each bit is independently 1 with probability \(\approx 1 - e^{-nT/m'}\):
\[\text{FPR} \approx \left(1 - e^{-nT/m'}\right)^T\]Let \(f = e^{-nT/m'}\) (the fraction of 0-bits). Then FPR \(= (1 - f)^T\). Taking the logarithm:
\[\ln(\text{FPR}) = T \ln(1 - f) = -\frac{m'}{n} f \ln f \cdot \frac{T \ln(1-f)}{-f \ln f \cdot m'/n}\]The function \(g(f) = f \ln(1/f)\) (which controls \(-f \ln f\)) reaches its maximum when we optimise over \(T\). Substituting \(T = -(m'/n) \ln f\) and differentiating with respect to \(f\):
\[\frac{d}{df}\left[-(m'/n) \ln f \cdot \ln(1-f)\right] = 0\]By symmetry of the expression in \(f\) and \(1-f\), the optimum is at \(f = 1/2\), i.e., half the bits are set. This gives:
\[T^* = \frac{m'}{n} \ln 2\]and the minimum FPR is:
\[\text{FPR}^* = (1/2)^{T^*} = 2^{-(m'/n) \ln 2} \approx 0.6185^{m'/n}\]With \(B = m'/n = 8\) bits per element:
- \(T^* = 8 \ln 2 \approx 5.55 \Rightarrow T = 6\)
- \(f = e^{-6/8} = e^{-0.75} \approx 0.472\)
- FPR \(\approx (1 - 0.472)^6 = (0.528)^6 \approx 0.0216 = 2.16\%\)
With \(B = 10\) bits per element: \(T^* \approx 7\), FPR \(\approx 0.82\%\).
With \(B = 16\) bits per element: \(T^* \approx 11\), FPR \(\approx 0.046\%\).
Math quiz
Chapter math quizzes are in the Quiz Hub. Filter by this chapter and choose Study / Math / All.