Hashing Collisions in a Student Records System
A school stores 10,000 student records in a hash table with 10,000 buckets, using the hash function h(key) = key mod 10,000 where key is the student ID (a 6-digit number). Collisions are resolved by linear probing (check the next bucket, wrapping around). The school observes that lookups for certain ID ranges are much slower than others, and that after filling to 9,500 records, some lookups take hundreds of probes. A developer suggests switching to chaining with linked lists and keeping the same hash function. Another suggests increasing the table to 20,000 buckets but keeping linear probing.
1. Explain why performance degrades so sharply as the load factor rises, using the observed numbers.
Read the worked answer
Linear probing performance depends critically on the load factor α = n/m. At n = 9,500 and m = 10,000, α = 0.95. For successful searches, linear probing averages about ½(1 + 1/(1−α)) probes; at α = 0.95 that is ½(1 + 20) = 10.5 probes on average, and unsuccessful searches average ½(1 + 1/(1−α)²) ≈ ½(1 + 400) = 200 probes. The observed 'hundreds of probes' matches the unsuccessful-search formula.
The deeper problem is primary clustering: linear probing fills contiguous runs of occupied buckets, and any key hashing into a run must probe to its end. Clusters grow and merge, so the cost is superlinear in α. The ID-range slowdown is explained by the hash function: h(key) = key mod 10,000 maps IDs differing by 10,000 to the same bucket, and sequential IDs map to sequential buckets, so nearby IDs form long runs. At α = 0.5 the same table would average about 2.5 probes for successful search - the degradation from 0.5 to 0.95 is dramatic, not linear.
2. Compare the two proposals (chaining with the same hash function, versus doubling buckets with linear probing) and recommend one with justification.
Read the worked answer
Chaining with the same hash function: the load factor stays 0.95, so average chain length is 0.95. Successful search averages about 1 + α/2 ≈ 1.48 probes, unsuccessful about α ≈ 0.95 - a large improvement over linear probing's 10.5 and 200. However, the hash function is still poor: IDs differing by 10,000 collide, and sequential IDs distribute unevenly if the ID space is structured. Chaining tolerates clustering better than linear probing because collisions become list nodes rather than contiguous runs, but a bad hash function still creates long chains for adversarial or structured keys.
Doubling buckets to 20,000 with linear probing: α drops to 0.475. Successful search averages ½(1 + 1/0.525) ≈ 1.45 probes; unsuccessful ≈ ½(1 + 1/0.525²) ≈ 2.3 probes. This is excellent and eliminates the pathological probing. The cost is memory (20,000 buckets) and rehashing all 9,500 records once.
Recommendation: doubling with linear probing gives the best probe counts and keeps cache-friendly contiguous storage, provided the hash function is also improved. I would recommend doubling and replacing the hash function (e.g. multiply-shift or a mixing function) so that IDs differing by 10,000 no longer collide. Chaining is a reasonable fallback if memory is tight, but it adds pointer overhead and does not fix the underlying hash weakness. The judgement is that neither proposal alone is sufficient: the load factor and the hash quality must both be addressed.
3. The school wants to guarantee O(1) worst-case lookup. Explain whether this is achievable and what it would require.
Read the worked answer
Ordinary hashing with chaining or probing gives O(1) expected time under a good hash function and bounded load factor, but O(n) worst case if all keys collide. To guarantee O(1) worst case, use a perfect hashing scheme.
For a static set (records that do not change), two-level perfect hashing (FKS) achieves O(1) worst-case lookup with O(n) space: a first-level hash into O(n) buckets, and each bucket with k items gets a second-level table of size k² with a hash function chosen to be collision-free for that bucket. Lookup is two hash computations, guaranteed. This is achievable for the school's 10,000 records if they are fixed.
For a dynamic set (insertions and deletions), guaranteed O(1) worst case is achievable with dynamic perfect hashing or cuckoo hashing (O(1) expected, O(1) worst case for lookup with high probability), but true deterministic worst-case O(1) under arbitrary insertions requires more elaborate structures (e.g. dynamic FKS). The practical answer: if records are static, FKS perfect hashing gives the guarantee; if dynamic, cuckoo hashing gives O(1) worst-case lookup with high probability, which is usually sufficient. The exam expects recognition that 'O(1)' is a claim about a model (expected vs worst case) and that the guarantee depends on whether the data set is static.