COMPX270 — Randomised and Advanced Algorithms
Chapter 6: Hashing and Friends
Dictionary ADT implementations, universal and strongly universal hash families, collision resolution (separate chaining, open addressing, cuckoo hashing), and Bloom filters with false-positive analysis.
Modular arithmetic, pigeonhole principle, birthday paradox, and Bloom filter probability analysis
Dictionary ADT
The Dictionary Problem
A dictionary stores a set \(S\) of elements from a universe \(X\) and supports three operations:
- Insert(x): Add element \(x\) to \(S\).
- Lookup(x): Return whether \(x \in S\) (and optionally associated data).
- Remove(x): Delete element \(x\) from \(S\).
We have \(|S| = n\) stored elements and a universe of size \(|X| = m\), where typically \(m \gg n\).
| Implementation | Insert | Lookup | Remove | Space |
|---|---|---|---|---|
| Unsorted Linked List | \(O(1)\) | \(O(n)\) | \(O(n)\) | \(O(n)\) |
| Direct-Address Array | \(O(1)\) | \(O(1)\) | \(O(1)\) | \(O(m)\) |
| Balanced BST | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(n)\) |
| Hash Table | \(O(1)\) exp. | \(O(1)\) exp. | \(O(1)\) exp. | \(O(n)\) |
Why Hashing?
A direct-address array gives \(O(1)\) operations but uses \(O(m)\) space, which is wasteful when \(m \gg n\). A balanced BST uses \(O(n)\) space but \(O(\log n)\) time. Hash tables achieve the best of both worlds: \(O(1)\) expected time and \(O(n)\) space — at the cost of using randomisation.
Hash Tables
The Idea
Instead of allocating an array of size \(m\) (universe size), we allocate a table of size \(m' = O(n)\) and use a hash function \(h : X \to Y\) where \(Y = \{0, 1, \ldots, m'-1\}\) to map each element to a table slot.
The fundamental problem: since \(|X| = m \gg m' = |Y|\), the function \(h\) cannot be injective. By the Pigeonhole Principle, there must exist distinct elements \(x \neq x'\) with \(h(x) = h(x')\). This is called a collision.
Key Parameters
- \(n\): number of elements stored
- \(m = |X|\): universe size
- \(m' = |Y|\): table size, chosen to be \(O(n)\)
- \(\alpha = n/m'\): load factor (fraction of table that is occupied)
Birthday Paradox Connection
Even for a random hash function mapping \(n\) elements to \(m'\) slots, collisions are nearly inevitable once \(n = \Omega(\sqrt{m'})\). This is exactly the birthday paradox: with \(\approx 23\) people (elements), there is a \(> 50\%\) chance of a shared birthday among 365 days (slots). For hash tables with \(m' = O(n)\), collisions are guaranteed, so we must handle them.
Hash Families
Why Families Instead of a Single Function?
For any fixed hash function \(h\), an adversary can choose \(n\) elements that all map to the same slot, making all operations \(O(n)\). The solution: pick \(h\) randomly from a family \(\mathcal{H}\) of functions. The adversary must choose elements before seeing which \(h\) was selected.
Definition: Universal Hash Family
A family \(\mathcal{H} \subseteq \{h : X \to Y\}\) is universal if for every pair of distinct elements \(x \neq x' \in X\):
\[\Pr_{h \sim \mathcal{H}}[h(x) = h(x')] \leq \frac{1}{|Y|} = \frac{1}{m'}\]In other words, the collision probability is at most what we would expect from a completely random function.
Definition: Strongly Universal Hash Family
A family \(\mathcal{H}\) is strongly universal (also called 2-independent) if for every pair of distinct elements \(x \neq x' \in X\) and every pair of values \(y, y' \in Y\):
\[\Pr_{h \sim \mathcal{H}}[h(x) = y \;\text{and}\; h(x') = y'] = \frac{1}{|Y|^2}\]This means \(h(x)\) and \(h(x')\) behave like independent uniform random variables over \(Y\).
Theorem 31: Strongly Universal via Polynomials
Let \(p\) be a prime with \(p \geq |X|\). For \(a, b \in \mathbb{Z}_p\), define:
\[h_{a,b}(x) = ax + b \pmod{p}\]Then \(\mathcal{H} = \{h_{a,b} : a, b \in \mathbb{Z}_p\}\) is a strongly universal family over \(\mathbb{Z}_p\).
Fix distinct \(x, x' \in \mathbb{Z}_p\) and target values \(y, y' \in \mathbb{Z}_p\). We need \(h_{a,b}(x) = y\) and \(h_{a,b}(x') = y'\), which gives the system:
\[ax + b \equiv y \pmod{p}\] \[ax' + b \equiv y' \pmod{p}\]Subtracting: \(a(x - x') \equiv y - y' \pmod{p}\). Since \(x \neq x'\) and \(p\) is prime, \((x - x')\) has an inverse mod \(p\), giving a unique \(a\). Then \(b = y - ax \pmod{p}\) is also uniquely determined.
So exactly one pair \((a, b)\) out of \(p^2\) satisfies both equations, giving probability \(1/p^2 = 1/|Y|^2\). \(\square\)
Theorem 32: Universal Hash Family Construction
Let \(p\) be a prime with \(p \geq m\). For \(a \in \mathbb{Z}_p \setminus \{0\}\) and \(b \in \mathbb{Z}_p\), define:
\[h_{a,b}(x) = ((ax + b) \bmod p) \bmod m'\]Then \(\mathcal{H} = \{h_{a,b}\}\) is a universal hash family mapping \(X \to \{0, \ldots, m'-1\}\).
Collision Handling
Separate Chaining
Each table slot contains a linked list of all elements that hash to that slot. Operations:
- Insert(x): Compute \(h(x)\), prepend \(x\) to list at slot \(h(x)\). Time: \(O(1)\).
- Lookup(x): Compute \(h(x)\), search the list at slot \(h(x)\). Time: \(O(\text{list length})\).
- Remove(x): Compute \(h(x)\), search and delete from list. Time: \(O(\text{list length})\).
Expected Performance with Universal Hashing
With a universal hash family and load factor \(\alpha = n/m'\), the expected time for Lookup and Remove is:
\[O(1 + \alpha)\]If \(m' = \Theta(n)\), then \(\alpha = O(1)\), giving expected \(O(1)\) per operation.
For a Lookup of element \(x\), the time is proportional to the length of the list at slot \(h(x)\). This list length equals \(1 + |\{y \in S \setminus \{x\} : h(y) = h(x)\}|\). By universality, for each \(y \neq x\):
\[\Pr[h(y) = h(x)] \leq \frac{1}{m'}\]By linearity of expectation, the expected number of collisions is:
\[\sum_{y \in S \setminus \{x\}} \Pr[h(y) = h(x)] \leq \frac{n - 1}{m'} < \alpha\]So the expected list length is at most \(1 + \alpha\). \(\square\)
Open Addressing
Instead of linked lists, all elements are stored directly in the table. When a collision occurs, we probe alternative slots according to a probe sequence \(h_1(x), h_2(x), h_3(x), \ldots\)
- Linear probing: \(h_i(x) = (h(x) + i) \bmod m'\). Simple, cache-friendly, but causes clustering.
- Double hashing: \(h_i(x) = (h_1(x) + i \cdot h_2(x)) \bmod m'\). Two independent hash functions reduce clustering.
Theorem 33: Open Addressing Expected Lookup
Under the uniform hashing assumption (each probe sequence is a uniformly random permutation), the expected number of probes for a lookup in an open-addressing hash table with load factor \(\alpha < 1\) is at most:
\[\frac{1}{1 - \alpha}\]The probability that the first probe hits an occupied slot is \(\alpha = n/m'\). Given that the first slot was occupied, the second probe hits an occupied slot with probability \((n-1)/(m'-1) < \alpha\). The expected number of probes is:
\[\sum_{i=0}^{\infty} \alpha^i = \frac{1}{1 - \alpha}\]More precisely, the probability of needing more than \(k\) probes is at most \(\alpha^k\), so \(E[\text{probes}] = \sum_{k=0}^{\infty} \Pr[\text{probes} > k] \leq \sum_{k=0}^{\infty} \alpha^k = 1/(1 - \alpha)\). \(\square\)
Theorem 34 (Knuth): Linear Probing
Under a uniform hash function, the expected number of probes for a lookup with linear probing and load factor \(\alpha < 1\) is:
\[O\!\left(\frac{1}{(1 - \alpha)^2}\right)\]Linear probing is slower than ideal open addressing due to primary clustering.
Cuckoo Hashing
The Power of Two Choices
Cuckoo hashing uses two hash tables \(T_1\) and \(T_2\) with two independent hash functions \(h_1\) and \(h_2\). Each element \(x\) can reside in either \(T_1[h_1(x)]\) or \(T_2[h_2(x)]\).
Cuckoo Hashing Operations
Lookup(x): Check \(T_1[h_1(x)]\) and \(T_2[h_2(x)]\). Time: worst-case \(O(1)\).
Remove(x): Check both locations, delete if found. Time: worst-case \(O(1)\).
Insert(x):
- If \(T_1[h_1(x)]\) is empty, place \(x\) there. Done.
- Otherwise, evict the current occupant \(y\) from \(T_1[h_1(x)]\), place \(x\) there.
- Try to insert \(y\) into its alternative location \(T_2[h_2(y)]\).
- If that slot is also occupied, evict and continue the chain.
- If a cycle is detected (or too many evictions), rehash with new hash functions.
Theorem 35: Cuckoo Hashing Performance
With table size \(m' \geq 2n\) (load factor \(\alpha \leq 1/2\)) and hash functions from a suitable family:
- Lookup and Remove: worst-case \(O(1)\).
- Insert: expected \(O(1)\) amortised.
Interactive: Cuckoo Hashing Simulator
Insert keys into a cuckoo hash table with two tables. Watch the kick chains as collisions are resolved.
Table 1 — h₁(x) = x mod 7
Table 2 — h₂(x) = ⌊x/7⌋ mod 7
Bloom Filters
Approximate Set Membership
A Bloom filter is a space-efficient probabilistic data structure that supports approximate set membership queries. It allows false positives but never false negatives.
Structure
- An array of \(m'\) bits, all initially 0.
- \(T\) independent hash functions \(h_1, h_2, \ldots, h_T : X \to \{0, \ldots, m'-1\}\).
Bloom Filter Operations
Insert(x): Set bits \(h_1(x), h_2(x), \ldots, h_T(x)\) to 1.
Lookup(x): Return “maybe in set” if ALL bits \(h_1(x), \ldots, h_T(x)\) are 1; return “definitely not in set” if any bit is 0.
False Positive Rate
After inserting \(n\) elements into a Bloom filter with \(m'\) bits and \(T\) hash functions, the false positive probability for a new element is approximately:
\[\text{FPR} \approx \left(1 - e^{-nT/m'}\right)^T\]The optimal number of hash functions that minimises the FPR is:
\[T^* = \frac{m'}{n} \ln 2 \approx 0.693 \cdot \frac{m'}{n}\]At this optimum, the FPR is \(\approx (1/2)^T \approx 0.6185^{m'/n}\).
After inserting one element, each of the \(T\) hash functions sets one bit. The probability that a specific bit remains 0 after one hash is \(1 - 1/m'\). After \(nT\) total hash operations:
\[\Pr[\text{bit } i = 0] = \left(1 - \frac{1}{m'}\right)^{nT} \approx e^{-nT/m'}\]So the probability that a specific bit is 1 is \(\approx 1 - e^{-nT/m'}\). A false positive occurs when all \(T\) bits for a non-member are 1:
\[\text{FPR} \approx \left(1 - e^{-nT/m'}\right)^T\]To minimise, let \(p = e^{-nT/m'}\) and note that FPR \(= (1 - p)^T = (1 - p)^{-(m'/n) \ln p \cdot (n/m') / \ln(1/p) \cdot T}\). Taking the derivative and setting to zero gives \(p = 1/2\), hence \(T^* = (m'/n) \ln 2\). \(\square\)
Space Complexity
A Bloom filter uses:
\[\text{Space} = O(T \log m + m') \text{ bits}\]where \(T \log m\) bits store the hash function descriptions and \(m'\) bits for the bit array. Compared to storing the actual set (\(O(n \log m)\) bits), the Bloom filter can be much more compact when the desired FPR is not too small.
Interactive: Bloom Filter Simulator
Insert elements and check for false positives. Watch how bits get set and observe the empirical false positive rate.
Summary & Comparison
| Structure | Lookup | Insert | Remove | Space | Notes |
|---|---|---|---|---|---|
| Separate Chaining | \(O(1+\alpha)\) exp. | \(O(1)\) | \(O(1+\alpha)\) exp. | \(O(n+m')\) | Simple, flexible \(\alpha\) |
| Open Addr. (double hash) | \(O(1/(1-\alpha))\) exp. | \(O(1/(1-\alpha))\) exp. | Tricky (tombstones) | \(O(m')\) | No pointers, cache-friendly |
| Linear Probing | \(O(1/(1-\alpha)^2)\) exp. | \(O(1/(1-\alpha)^2)\) exp. | Tricky | \(O(m')\) | Clustering, but cache-optimal |
| Cuckoo Hashing | \(O(1)\) worst | \(O(1)\) exp. | \(O(1)\) worst | \(O(n)\) | Requires \(\alpha < 1/2\) |
| Bloom Filter | \(O(T)\) | \(O(T)\) | Not supported | \(O(m')\) bits | Approximate, false positives |
Key Takeaways
- Universal hashing guarantees expected \(O(1)\) operations regardless of the input distribution — only the random choice of \(h\) matters.
- Strongly universal (2-independent) hash families enable tighter analyses and can be constructed via linear functions over \(\mathbb{Z}_p\).
- Cuckoo hashing achieves worst-case \(O(1)\) Lookup and Remove by using two hash functions and displacement chains.
- Bloom filters trade exactness for extreme space efficiency. The optimal number of hash functions is \(T^* = (m'/n) \ln 2\).
- The load factor \(\alpha = n/m'\) is the central parameter governing performance in all hashing schemes.
Tutorial Problems
Work through these problems to solidify your understanding of hashing and Bloom filters.
Problem 1 Warm-up
Compare and contrast hash tables and Bloom filters. Under what circumstances would you choose a Bloom filter over a hash table?
Hash Table: Stores exact data, supports Insert/Lookup/Remove, uses \(O(n)\) words of space, and gives exact answers.
Bloom Filter: Does not store actual elements, supports Insert and approximate Lookup only (no Remove), uses \(O(m')\) bits of space, and may return false positives.
Choose a Bloom filter when:
- Memory is extremely limited (e.g., network routers, mobile devices).
- A small false positive rate is acceptable.
- You do not need to remove elements or retrieve associated data.
- The universe is very large (e.g., checking if a URL has been visited).
\(\square\)
Problem 2 Warm-up
Prove that the expected time for a Lookup in a hash table with separate chaining and a universal hash family is \(O(1 + \alpha)\), where \(\alpha = n/m'\).
Let \(x\) be the element we are looking up, and \(S\) be the set of \(n\) stored elements. The lookup time is proportional to the length of the chain at slot \(h(x)\).
Define indicator random variables \(I_y = \mathbf{1}[h(y) = h(x)]\) for each \(y \in S \setminus \{x\}\). The chain length is:
\[L = 1 + \sum_{y \in S \setminus \{x\}} I_y\]By universality, \(\mathbb{E}[I_y] = \Pr[h(y) = h(x)] \leq 1/m'\). By linearity of expectation:
\[\mathbb{E}[L] \leq 1 + \sum_{y \in S \setminus \{x\}} \frac{1}{m'} = 1 + \frac{n-1}{m'} < 1 + \alpha\]Therefore the expected lookup time is \(O(1 + \alpha)\). When \(m' = \Theta(n)\), this is \(O(1)\). \(\square\)
Problem 3 Warm-up
Give an example of a universal hash family where the collision probability is strictly less than \(1/|Y|\) for some pairs of elements. (That is, universality only requires \(\leq 1/|Y|\), but equality is not always achieved.)
Consider the identity function family \(\mathcal{H} = \{h_{\text{id}}\}\) where \(h_{\text{id}}(x) = x\) on domain \(X = Y = \{0, 1, \ldots, m'-1\}\). Then for any distinct \(x \neq x'\):
\[\Pr[h(x) = h(x')] = 0 < \frac{1}{m'}\]This is trivially universal (with strict inequality), but it is a degenerate example since \(|X| = |Y|\) (no compression). A more interesting example: take the strongly universal family \(\{h_{a,b}(x) = (ax+b \bmod p)\}\) on \(\mathbb{Z}_p\). The collision probability is exactly \(0\) for all distinct pairs, which is strictly less than \(1/p\). Universality is easily satisfied with strict inequality when the intermediate domain is at least as large as the input domain. \(\square\)
Problem 4 Problem Solving ⭐
Given three arrays \(A[1..n]\), \(B[1..n]\), \(C[1..n]\) of integers, determine whether there exist indices \(i, j, k\) such that \(A[i] + B[j] = C[k]\). Give an \(O(n^2)\) expected-time algorithm using hashing.
Algorithm:
- Insert all elements of \(C\) into a hash table \(H\). Time: \(O(n)\) expected.
- For each pair \((i, j)\) with \(1 \leq i, j \leq n\):
- Compute \(s = A[i] + B[j]\).
- Lookup \(s\) in \(H\). If found, return “YES”.
- Return “NO”.
Analysis: Step 1 takes \(O(n)\) expected time with universal hashing. Step 2 iterates over \(n^2\) pairs, each requiring an \(O(1)\) expected-time lookup. Total: \(O(n^2)\) expected time.
Without hashing, the best comparison-based approach is \(O(n^2 \log n)\) (sort \(C\), then binary search for each sum). \(\square\)
Problem 5 Problem Solving ⭐
(Perfect Hashing) Design a hash table with \(O(n)\) space and worst-case \(O(1)\) lookup time for a static set of \(n\) elements. (Hint: use a two-level scheme.)
FKS (Fredman–Komlós–Szemerédi) Perfect Hashing:
- First level: Use a universal hash function \(h\) to map \(n\) elements into \(m' = O(n)\) buckets. Let \(n_i\) be the number of elements in bucket \(i\).
- Second level: For each bucket \(i\), create a separate hash table of size \(n_i^2\) using another universal hash function \(h_i\). With probability \(\geq 1/2\), there are no collisions at the second level (birthday paradox in reverse: \(n_i\) elements into \(n_i^2\) slots).
Space analysis: The total space for the second level is:
\[\sum_{i=0}^{m'-1} O(n_i^2)\]A key result from universal hashing: \(\mathbb{E}\left[\sum n_i^2\right] \leq n + n(n-1)/m'\). With \(m' = cn\) for a suitable constant \(c\), this is \(O(n)\).
Lookup: Compute \(h(x)\) to find the bucket, then \(h_{h(x)}(x)\) to find the slot within the bucket. Two hash computations, each \(O(1)\), giving worst-case \(O(1)\) lookup. \(\square\)
Problem 6 Problem Solving ⭐
A Bloom filter has \(m' = 8n\) bits (i.e., \(B = 8\) bits per element). What is the optimal number of hash functions \(T\)? What is the resulting false positive rate?
Optimal \(T\):
\[T^* = \frac{m'}{n} \ln 2 = 8 \cdot \ln 2 \approx 8 \times 0.693 = 5.545\]Since \(T\) must be an integer, we use \(T = 6\).
False positive rate with \(T = 6\):
\[\text{FPR} \approx \left(1 - e^{-nT/m'}\right)^T = \left(1 - e^{-6/8}\right)^6 = \left(1 - e^{-0.75}\right)^6\] \[e^{-0.75} \approx 0.4724\] \[\text{FPR} \approx (1 - 0.4724)^6 = (0.5276)^6 \approx 0.0216 \approx 2.16\%\]So with only 8 bits per element and 6 hash functions, the false positive rate is about 2.16%. \(\square\)
Problem 7 Advanced ⭐⭐
(Counting Bloom Filter) Standard Bloom filters do not support Remove. Propose a modification that supports Remove. What is the trade-off?
Counting Bloom Filter: Replace each bit with a small counter (e.g., 4 bits). Operations:
- Insert(x): Increment counters at positions \(h_1(x), \ldots, h_T(x)\).
- Lookup(x): Return “maybe” if all counters at \(h_1(x), \ldots, h_T(x)\) are \(> 0\).
- Remove(x): Decrement counters at positions \(h_1(x), \ldots, h_T(x)\).
Correctness: Each counter tracks the number of elements hashing to that position. Decrementing on Remove undoes the Insert, preserving correctness for other elements. The “never false negatives” property is maintained as long as we only remove elements that were previously inserted.
Trade-off: Space increases by a factor of \(c\) (the counter width). With 4-bit counters, space is \(4 \times\) that of a standard Bloom filter. Counter overflow is possible but very unlikely in practice (a 4-bit counter handles up to 15 collisions). \(\square\)
Chapter quizzes
Self-test and math questions for this chapter are in the Quiz Hub (practice or exam mode).