Hash Tables & Collision Resolution theory

The Simple Uniform Hashing Assumption (SUHA) is a theoretical model positing that a hash function h maps every key k from a key universe U into table slots {0, 1, ..., m − 1} such that: (1) Each key is equally likely to hash to any of the m slots, meaning Pr[h(k) = j] = 1/m for all j ∈ [0, m − 1]; and (2) The hash value h(k₁) of any key is statistically independent of the hash value h(k₂) of any other key, regardless of key patterns or similarities. Under SUHA, the distribution of n keys across m slots follows a multinomial distribution that closely approximates a Poisson distribution with parameter λ = α = n/m for large m. SUHA provides the mathematical foundation for proving that the expected chain length in Separate Chaining is exactly α, and that the expected probe length in Open Addressing with uniform probing is 1 / (1 − α). In practical systems, deterministic hash functions cannot achieve true statistical randomness for all possible inputs; however, Universal Hash Families (introduced by Carter and Wegman in 1979) and modern high-quality hash functions (such as MurmurHash3, CityHash, xxHash, and SipHash) achieve pseudo-random avalanche characteristics where flipping a single input bit flips approximately 50% of output hash bits, effectively satisfying SUHA for non-adversarial real-world workloads.

Separate Chaining (Closed Addressing) and Open Addressing represent two fundamentally divergent architectural philosophies for resolving hash collisions: (1) Memory Layout and Capacity Constraints: Separate Chaining maintains an array of m head pointers; each collided key is stored in an externally allocated linked list node. Consequently, Separate Chaining imposes no upper bound on key count n, gracefully tolerating load factors α = n/m > 1 (e.g., α = 2.0 or 5.0). In contrast, Open Addressing stores all keys directly within the primary contiguous array buffer of capacity m. This establishes a strict physical ceiling where n < m (load factor α < 1.0); attempting to insert n = m keys results in table saturation and infinite search loops unless dynamic rehashing is triggered. (2) Microarchitectural CPU Cache Hierarchy Locality: In Separate Chaining, every node insertion requires a heap allocation via malloc(). Linked nodes are scattered across arbitrary non-contiguous virtual memory addresses. Traversing a chain requires chasing pointers (node = node->next), which frequently incurs cold CPU L1/L2 data cache misses and Translation Lookaside Buffer (TLB) page table walks, taking ~100–250 CPU clock cycles per hop. In Open Addressing (particularly Linear Probing), all entries are packed into contiguous memory. When slot i is accessed, the CPU hardware prefetcher loads the entire 64-byte cache line containing 8 consecutive 64-bit slots into L1 cache, allowing sequential probe comparisons to execute in sub-nanosecond L1 cache hit times (~1–4 clock cycles). (3) Degradation at High Load Factors: In Separate Chaining, search cost scales linearly with load factor: E[P] = 1 + α/2 for successful search and E[P] = α for unsuccessful search. Even at α = 2.0, an average search requires only ~2 probes. In Open Addressing, search latency exhibits a non-linear asymptotic divergence as α approaches 1.0. Under Double Hashing, E[P] = 1 / (1 − α), meaning probe length explodes from 2.0 at α = 0.50 to 10.0 at α = 0.90, and diverges toward infinity as α → 1.0. Under Linear Probing, primary clustering causes an even more severe quadratic explosion: E[P] ≈ 0.5(1 + 1/(1-α)²), reaching 50.5 probes at α = 0.90.

Primary Clustering is a pathological phenomenon inherent to Linear Probing h(k, i) = (h(k) + i) mod m wherein contiguous blocks of occupied slots coalesce into expanding continuous clusters. The fundamental mechanism driving cluster growth is asymmetric probabilistic attraction: Consider a hash table of capacity m containing an isolated contiguous run of L occupied slots spanning indices j through j + L − 1. For an incoming key k, what is the probability that slot j + L (the empty slot immediately following the cluster) will be filled? A key will be inserted at j + L if its initial hash h(k) hits slot j + L directly (probability 1/m), OR if h(k) hits ANY of the L occupied slots in the cluster (j, j+1, ..., j+L-1), because linear probing forces the key to step sequentially through the entire cluster until reaching j + L (probability L/m). Therefore, the total probability of slot j + L being filled is (L + 1)/m. This means that a cluster of length L = 10 is eleven times more likely to grow on the next insertion than an isolated empty slot! Larger clusters grow proportionally faster than smaller clusters, acting as 'gravitational attractors' that sweep up incoming keys and bridge previously separate clusters into massive monolithic blocks. In 1962, Donald Knuth published the first rigorous mathematical analysis of Linear Probing, deriving the expected number of probes in an unsuccessful search: E[P_unsuccessful] ≈ (1/2) · [1 + 1 / (1 − α)²], and in a successful search: E[P_successful] ≈ (1/2) · [1 + 1 / (1 − α)]. The critical term is the quadratic denominator (1 − α)⁻². While uniform hashing requires 1 / (1 − α) probes, Linear Probing squares the load deficit penalty. At α = 0.50, uniform hashing requires 2.0 probes while linear probing requires 2.5 probes. But at α = 0.80, uniform hashing requires 5.0 probes while linear probing requires 13.0 probes; and at α = 0.90, uniform hashing requires 10.0 probes while linear probing explodes to 50.5 probes.

Double Hashing eliminates both primary and secondary clustering by utilizing two distinct hash functions, h₁(k) and h₂(k), to define the probe sequence: h(k, i) = (h₁(k) + i · h₂(k)) mod m, where i = 0, 1, 2, ..., m − 1. (1) Elimination of Primary Clustering: Unlike Linear Probing where the probe offset is always 1, Double Hashing advances by a dynamic stride h₂(k). Colliding keys do not advance along adjacent slots, preventing contiguous occupied blocks from merging or acting as gravitational attractors. (2) Elimination of Secondary Clustering: In Quadratic Probing h(k, i) = (h(k) + c₁i + c₂i²) mod m, primary clustering is eliminated, but secondary clustering occurs: any two distinct keys k₁ and k₂ that hash to the same initial slot h(k₁) = h(k₂) trace the exact same sequence of quadratic offsets. Double Hashing solves this because the probe stride h₂(k) is computed independently of h₁(k). If two keys collide at h₁(k₁) = h₁(k₂), they will almost certainly produce different strides h₂(k₁) ≠ h₂(k₂). Thus, their probe sequences diverge immediately at i = 1, exploring the table along completely different cyclic permutations. (3) Full Cycle Traversal Condition: For Double Hashing to successfully locate an empty slot anywhere in the table, the probe sequence must generate a complete permutation of the residue classes modulo m. By elementary group theory, the sequence {i · h₂(k) mod m} for i ∈ [0, m − 1] generates all m distinct residues if and only if the step size h₂(k) is coprime to the table size m: gcd(h₂(k), m) = 1. If gcd(h₂(k), m) = d > 1, the probe sequence would cycle through only m/d slots, potentially reporting that the table is full when m − m/d slots remain completely empty! In systems design, this coprimality condition is satisfied by one of two strategies: (a) Choose table capacity m as a prime number, and set h₂(k) = 1 + (k mod (m − 1)), guaranteeing that 1 ≤ h₂(k) < m and gcd(h₂(k), m) = 1; or (b) Choose table capacity m as a power of two (m = 2^p), and force h₂(k) to always be odd by setting h₂(k) = (hash(k) << 1) | 1, because any odd integer is coprime to 2^p.

Under the Uniform Hashing Assumption (or uniform open addressing), the probe sequence ⟨h(k, 0), h(k, 1), ..., h(k, m − 1)⟩ is assumed to be a uniformly distributed random permutation of {0, 1, ..., m − 1}, chosen independently for each key. Consider an unsuccessful search for key k in a table with capacity m containing n occupied slots (load factor α = n/m). The search inspects slots h(k, 0), h(k, 1), ... until encountering the first unoccupied (NULL) slot. Let random variable X denote the number of probes performed. Probe 1 always occurs: Pr[X ≥ 1] = 1. Probe 2 occurs if and only if probe 1 hits an occupied slot. Since n of the m slots are occupied, Pr[X ≥ 2] = n / m = α. Probe 3 occurs if both probe 1 and probe 2 hit occupied slots. Since probe 2 inspects an occupied slot chosen uniformly from the remaining m − 1 slots of which n − 1 are occupied: Pr[X ≥ 3] = (n / m) · ((n − 1) / (m − 1)). In general, for any integer i ≥ 1: Pr[X ≥ i] = (n / m) · ((n − 1) / (m − 1)) ··· ((n − i + 2) / (m − i + 2)). Because n/m = α and (n − j)/(m − j) < n/m for all j ≥ 1, we obtain the upper bound: Pr[X ≥ i] ≤ (n / m)^{i − 1} = α^{i − 1}. The expected value of any non-negative integer-valued random variable X is given by the tail probability sum formula: E[X] = ∑_{i=1}^{∞} Pr[X ≥ i]. Substituting our tail bound: E[P_unsuccessful] = ∑_{i=1}^{∞} Pr[X ≥ i] ≤ ∑_{i=1}^{∞} α^{i − 1} = ∑_{j=0}^{∞} α^j. Since α < 1 in open addressing, this infinite geometric series converges exactly: ∑_{j=0}^{∞} α^j = 1 / (1 − α). Therefore, the expected number of probes in an unsuccessful search under uniform hashing is strictly bounded by E[P_unsuccessful] = 1 / (1 − α). Furthermore, a successful search for key k traces the exact probe sequence that was executed when key k was originally inserted. If key k was the (i + 1)-th element inserted into the table, the load factor at the time of its insertion was i / m. The expected probe cost to insert key k was therefore 1 / (1 − i/m). Averaging over all n keys currently stored in the table: E[P_successful] = (1/n) ∑_{i=0}^{n-1} 1 / (1 − i/m) = (m/n) ∑_{i=0}^{n-1} 1 / (m − i) = (1/α) ∑_{k=m-n+1}^{m} (1/k). Approximating the harmonic sum with the definite integral: E[P_successful] ≈ (1/α) ∫_{0}^{α} (1 / (1 − x)) dx = (1/α) ln(1 / (1 − α)).

For decades, traditional computer science curricula and standard library implementations (such as Java's java.util.HashMap and early C++ std::unordered_map) relied on Separate Chaining as the default hash table architecture. However, in modern computer architectures, the gap between CPU execution speed (~4.0 GHz) and main memory DRAM latency (~70–100 ns) has created the 'Memory Wall'. A single DRAM cache miss wastes 200–300 CPU clock cycles. In Separate Chaining, every node insertion requires a heap allocation, scattering nodes across memory. Even when load factor is low, chasing linked list pointers incurs inevitable L1/L2 cache misses. Modern production libraries—pioneered by Google's Abseil Swiss Tables (absl::flat_hash_map), adopted as the default standard library hash map in Rust (hashbrown), and mirrored in Python 3.6+ compact dictionaries—abandoned separate chaining in favor of cache-dense open addressing accelerated by SIMD (Single Instruction, Multiple Data) vector instructions. Swiss Tables split the hash table into two separate arrays: (1) A data slot array storing key-value pairs contiguously; and (2) A parallel control byte array storing 1-byte metadata per slot. When a 64-bit key hash is computed, it is partitioned into two parts: a 57-bit H1 index used to locate a group of 16 slots, and a 7-bit H2 fingerprint stored in the control byte (with special sentinel values: 0xFF for EMPTY, 0xFE for DELETED). Probing is executed in 16-slot chunks using a single 128-bit SIMD vector instruction (e.g., SSE2 _mm_cmpeq_epi8 on x86 or NEON on ARM). In exactly 1 CPU clock cycle, the processor broadcasts the 7-bit target fingerprint across a 128-bit register and compares it simultaneously against all 16 control bytes. A bitmask instruction (_mm_movemask_epi8) extracts the matching positions. In over 99% of queries, empty slots or non-matching keys are rejected in a single CPU cycle without ever accessing the primary key-value data array, eliminating cache misses entirely and achieving up to 3× faster lookup throughput than Separate Chaining.

Standard open addressing hash tables suffer from high variance in probe depth: while average probe length may be low, individual keys inserted late into crowded clusters can experience long probe sequences of O(n) in pathological cases. Two major algorithmic innovations resolve this tail latency: (1) Robin Hood Hashing: Named after the folklore hero who 'stole from the rich and gave to the poor', Robin Hood Hashing modifies open addressing insertion to minimize probe length variance. Each key in the table records its 'Distance from Home' (DFH), which is the number of probe steps it has traveled from its initial hash slot h(k). During insertion of an incoming key k_in, the algorithm probes forward. If it encounters an occupied slot containing key k_curr, it compares their probe distances: if DFH(k_in) > DFH(k_curr), the incoming key is deemed 'poorer' than the current occupant. The algorithm swaps the keys, placing k_in in the slot, and continues the insertion process by 'sinking' k_curr (with DFH incremented) into subsequent slots. Robin Hood Hashing dramatically compresses the probe distribution: the standard deviation of probe lengths shrinks toward zero, eliminating long search tails and allowing search queries to terminate early if an occupied slot is encountered whose DFH is smaller than the search key's current probe depth. (2) Cuckoo Hashing: Proposed by Pagh and Rodler in 2001, Cuckoo Hashing provides deterministic O(1) worst-case lookup time. It uses two separate hash tables, T₁ and T₂, and two independent hash functions, h₁(k) and h₂(k). A key k is guaranteed to reside in either T₁[h₁(k)] OR T₂[h₂(k)]. A lookup query inspects at most 2 memory locations: if the key is not at T₁[h₁(k)] and not at T₂[h₂(k)], it is guaranteed not to exist in the table. Insertion mimics the cuckoo bird: key k is placed at T₁[h₁(k)]. If that slot is already occupied by key y, key y is kicked out ('evicted') and moved to its alternative slot in T₂[h₂(y)]. If that slot is occupied by z, z is evicted to T₁[h₁(z)]. This displacement chain continues until an empty slot is found or a cycle is detected, at which point the table is rehashed with new hash functions. Cuckoo hashing achieves unmatched O(1) worst-case search latency for read-heavy workloads.