Difficulty: Advanced | Prerequisites: Arrays, linked lists, Big-O analysis, basic probability
This final block ties together several ideas: hash tables give you O(1) average-case dictionary operations, but understanding why requires probability. Skip lists use randomisation to achieve balanced-tree performance without rotations. Bloom filters and counting sketches trade exactness for massive space savings. Cardinality estimation (HyperLogLog-style ideas) shows how you can count distinct elements in a stream using almost no memory. These topics round out the course by showing that randomness is not a weakness but a powerful design tool.
TL;DR: Hash tables map keys to array indices for O(1) average-case operations. Collisions are handled by chaining or open addressing. Probabilistic structures like skip lists, Bloom filters, and counting sketches use randomness to achieve performance or space guarantees that deterministic structures cannot match.
Hash function
A function that maps a key to an integer (hash code), which is then mapped to an array index. A good hash function distributes keys uniformly across the table.
Hash table
An array-based data structure that uses a hash function to map keys to indices, providing O(1) average-case insert, find, and remove.
Collision
When two different keys map to the same array index. Every hash table must have a strategy for handling collisions.
Separate chaining
Handle collisions by storing a linked list (or other collection) at each array index. Multiple keys at the same index live in the same list.
Open addressing
Handle collisions by probing for the next open slot in the array. Variants include linear probing, quadratic probing, and double hashing.
Linear probing
When a collision occurs, check the next index, then the next, and so on (index + 1, index + 2, ...) until an empty slot is found. Suffers from primary clustering.
Quadratic probing
Probe at index + 1², index + 2², index + 3², etc. Reduces primary clustering but can suffer from secondary clustering.
Double hashing
Use a second hash function to determine the probe step size. Avoids both primary and secondary clustering.
Load factor (α)
The ratio of the number of elements to the table size: α = n / m. Performance degrades as α increases. With separate chaining, α can exceed 1. With open addressing, α must stay below 1.
Rehashing (resizing)
When the load factor exceeds a threshold (commonly 0.7 for open addressing, 1.0 or higher for chaining), create a larger table and reinsert all elements. Amortised O(1) per insertion.
Primary clustering
In linear probing, consecutive occupied slots form long clusters. A new key hashing into any slot in the cluster must probe to the end, making the cluster grow faster. A vicious cycle.
SUHA (Simple Uniform Hashing Assumption)
The assumption that each key is equally likely to hash to any of the m slots, independently of other keys. A theoretical convenience for analysis.
Skip list
A randomised data structure built from multiple levels of sorted linked lists. Higher levels skip over elements, providing O(log n) expected search time. Think of it as a probabilistic alternative to balanced BSTs.
Bloom filter
A space-efficient probabilistic data structure that tests set membership. It may report false positives (saying an element is present when it is not) but never false negatives. Uses a bit array and multiple hash functions.
False positive rate
The probability that a Bloom filter incorrectly reports an element as present. Depends on the bit array size, the number of hash functions, and the number of elements inserted.
Counting Bloom filter
A variant of a Bloom filter that uses counters instead of single bits at each position, allowing deletion of elements. Standard Bloom filters do not support deletion.
Count-Min Sketch
A probabilistic data structure for estimating the frequency of events in a stream. Uses multiple hash functions and a 2D array of counters. May overestimate counts but never underestimates.
Cardinality estimation
Estimating the number of distinct elements in a data stream without storing all elements. HyperLogLog is the classic algorithm, using O(log log n) space.
Jaccard similarity
The ratio of the size of the intersection to the size of the union of two sets: J(A, B) = |A ∩ B| / |A ∪ B|. Used to measure how similar two sets are. MinHash is a technique for estimating Jaccard similarity efficiently.
Requirements: deterministic (same key always gives same hash), uniform distribution, fast to compute
Common approach for integers: h(k) = k mod m, where m is the table size. Choosing m as a prime number far from a power of 2 helps avoid patterns.
Common approach for strings: treat the string as a polynomial. For example: h(s) = (s[0] · 31^(n-1) + s[1] · 31^(n-2) + ... + s[n-1]) mod m
Universal hashing: pick the hash function randomly from a family of functions at runtime. Guarantees expected O(1) performance regardless of input distribution.
Each table slot holds a linked list
Insert: hash the key, append to the list at that index. O(1)
Find: hash the key, search the list at that index. O(1 + α) expected, where α is the load factor
Remove: hash the key, find and remove from the list. O(1 + α) expected
Works well even when α > 1, though long chains degrade performance
Resize when α exceeds a threshold (typically around 1.0 to 2.0)
All elements live directly in the array (no linked lists)
Linear probing: h(k, i) = (h(k) + i) mod m
Simple but suffers from primary clustering
Deletion is tricky: you cannot just set a slot to empty (would break probe chains). Use a "deleted" tombstone marker.
Quadratic probing: h(k, i) = (h(k) + c₁·i + c₂·i²) mod m
Reduces primary clustering
Table size must be prime and load factor below 0.5 to guarantee finding an empty slot
Double hashing: h(k, i) = (h₁(k) + i · h₂(k)) mod m
Best distribution among linear methods
h₂(k) must never be 0 and should be coprime with m
Resize when α approaches 0.7 or higher (performance degrades significantly past this point)
Under SUHA with separate chaining, the expected time for an unsuccessful search is O(1 + α)
Under SUHA with separate chaining, the expected time for a successful search is O(1 + α/2)
For open addressing with load factor α: expected probes for unsuccessful search ≈ 1/(1 - α); for successful search ≈ (1/α) · ln(1/(1 - α))
As α approaches 1, open addressing performance degrades dramatically
Expected value: the weighted average of all possible outcomes. E[X] = Σ x · P(X = x)
Linearity of expectation: E[X + Y] = E[X] + E[Y], even when X and Y are not independent. This is used heavily in the analysis of randomised algorithms.
Indicator random variables: let X_i = 1 if event i occurs, 0 otherwise. Then E[X_i] = P(event i). The expected number of events is Σ E[X_i].
These tools are how you prove that hash table operations are O(1) on average, that skip lists are O(log n), and that Bloom filter false positive rates match their formulas.
Structure: multiple levels of sorted linked lists. The bottom level contains all elements. Each higher level contains a random subset (each element is "promoted" with probability 1/2).
Search: start at the top level, move right until you overshoot, then drop down a level. Repeat.
Expected height: O(log n) levels
Expected search time: O(log n)
Insert: insert at the bottom, then flip a coin repeatedly to decide how many levels to promote the new element into
Delete: remove the element from all levels it appears in
Advantages over balanced BSTs: simpler to implement, no rotations, easy concurrent access
Disadvantage: probabilistic guarantees, not worst-case
Structure: a bit array of size m, initialised to all 0s, with k independent hash functions
Insert: hash the element with all k functions, set those k bit positions to 1
Query: hash the element with all k functions, check those k positions. If all are 1, report "possibly present." If any is 0, report "definitely not present."
No false negatives: if the element was inserted, all k bits were set, so the query always returns true
False positives: other elements may have set the same bits, causing a spurious "present" result
Cannot delete: setting a bit to 0 might remove evidence of other elements
False positive probability (approximate): (1 - e^(-kn/m))^k, where n is the number of inserted elements
Optimal k: k = (m/n) · ln 2, which minimises the false positive rate for given m and n
Counting Bloom filter: replace each bit with a counter (typically 4 bits). Increment on insert, decrement on delete. Allows deletion but uses more space.
Count-Min Sketch: uses d hash functions and a d × w array of counters. To insert element x, increment counter[i][h_i(x)] for each hash function i. To query frequency of x, return the minimum of counter[i][h_i(x)] across all i. May overestimate but never underestimates.
Cardinality estimation: estimate the number of distinct elements in a stream
Flajolet-Martin idea: hash each element, count trailing zeros. The maximum number of trailing zeros observed gives an estimate of log₂(distinct count).
HyperLogLog refines this with multiple buckets and harmonic mean, achieving O(log log n) space for n distinct elements
MinHash and Jaccard similarity
To estimate J(A, B) = |A ∩ B| / |A ∪ B| without computing the full intersection and union
Apply a random hash function h to all elements. The minimum hash value of a set is called its MinHash.
P(min(h(A)) = min(h(B))) = J(A, B)
Use multiple hash functions and average to get a better estimate
Load factor:
α = n / m (elements / table size)
Bloom filter false positive rate:
P(false positive) ≈ (1 - e^(-kn/m))^k
Optimal number of hash functions for Bloom filter:
k_opt = (m / n) · ln 2 ≈ 0.693 · (m / n)
Expected probes for open addressing (unsuccessful search):
E[probes] ≈ 1 / (1 - α)
Expected probes for open addressing (successful search):
E[probes] ≈ (1/α) · ln(1 / (1 - α))
Skip list expected levels:
O(log n)
HyperLogLog space:
O(log log n) bits per bucket, with ~1/√m relative error using m buckets
Hash tables are everywhere: Python dictionaries, JavaScript objects, database indexing, caches, and symbol tables in compilers. Bloom filters are used in web browsers to check URLs against a database of malicious sites, in databases (like Cassandra and LevelDB) to avoid unnecessary disk reads, and in network routers. Count-Min Sketches are used in network traffic monitoring and database query optimisation. HyperLogLog is used by Redis, Google BigQuery, and analytics platforms to count unique visitors or distinct values in massive datasets.
"A good hash function prevents all collisions." With n elements and m slots, collisions are inevitable once n approaches m (and statistically likely much sooner, by the birthday paradox). The goal is to distribute collisions evenly.
"Open addressing is always better than chaining because it avoids linked list overhead." At high load factors, open addressing degrades severely due to clustering. Chaining degrades more gracefully.
"Bloom filters can return false negatives." They cannot. If an element was inserted, all its bits are set, so the query always returns "possibly present."
"A skip list always has O(log n) search." The O(log n) bound is expected (with high probability), not worst-case. In the worst case (extremely unlikely), all elements could be at the same level.
⚠️ Be able to insert into and search a hash table using separate chaining, linear probing, and quadratic probing. Show the state of the table after each operation.
⚠️ Understand primary clustering in linear probing and why it degrades performance.
⚠️ Calculate the false positive rate of a Bloom filter given m, n, and k.
⚠️ Know the difference between what Bloom filters guarantee (no false negatives) and what they cannot guarantee (no false positives).
⚠️ Be able to trace through skip list search and insertion, including the coin-flip promotion process.
⚠️ Understand when to resize a hash table and the amortised cost of rehashing.
⚠️ Probability tools (expected value, linearity of expectation, indicator variables) may appear as proof questions.
True or false: A Bloom filter can produce false negatives.
Fill in the blank: The load factor of a hash table is defined as ______.
True or false: In linear probing, you can simply set a deleted slot to empty.
Fill in the blank: The expected search time in a skip list is ______.
True or false: Count-Min Sketch can underestimate the frequency of an element.
Answers: 1. False. 2. n / m (number of elements divided by table size). 3. False (use a tombstone marker). 4. O(log n). 5. False (it may overestimate but never underestimates).
Q: Insert keys 10, 22, 31, 4, 15 into a hash table of size 7 using h(k) = k mod 7 with linear probing. Show the final table.
A: 10 mod 7 = 3 → slot 3. 22 mod 7 = 1 → slot 1. 31 mod 7 = 3 → collision, probe to slot 4. 4 mod 7 = 4 → collision, probe to slot 5. 15 mod 7 = 1 → collision, probe to slot 2. Final table: [_, 22, 15, 10, 31, 4, _] (indices 0 through 6).
Q: A Bloom filter uses m = 100 bits, k = 3 hash functions, and has n = 10 elements inserted. What is the approximate false positive rate?
A: P ≈ (1 - e^(-3·10/100))^3 = (1 - e^(-0.3))^3 ≈ (1 - 0.741)^3 = (0.259)^3 ≈ 0.017, or about 1.7%.
Q: Why can a standard Bloom filter not support deletion?
A: Setting a bit to 0 might remove evidence of other elements that also hash to that position. You would introduce false negatives, which breaks the fundamental guarantee of the data structure. Counting Bloom filters solve this by using counters instead of bits.
Q: Explain why a skip list's expected search time is O(log n).
A: At each level, you expect to skip about half the remaining elements (since each element is promoted with probability 1/2). With O(log n) levels and O(1) expected work per level (you move right a constant expected number of times before dropping down), the total expected search time is O(log n).
Hash tables connect to the amortised analysis ideas from dynamic arrays (Week 2) via rehashing. The probability material underpins the analysis of all randomised structures in this section and also connects to the analysis of randomised quicksort (often covered in algorithms courses). Bloom filters and sketches are practical examples of space-time tradeoffs, a theme that runs through the entire course. The hash functions used here are the same ones used in disjoint set hashing, consistent hashing in distributed systems, and cryptographic applications.
hash table, hash map, hash function, collision, separate chaining, open addressing, linear probing, quadratic probing, double hashing, load factor, rehashing, resizing, primary clustering, secondary clustering, SUHA, universal hashing, skip list, randomised data structure, Bloom filter, false positive, false negative, counting Bloom filter, Count-Min Sketch, cardinality estimation, HyperLogLog, Flajolet-Martin, MinHash, Jaccard similarity, probability, expected value, linearity of expectation, indicator variable, CS 225, data structures, UIUC