Collision Handling
Collision handling is the set of techniques used to resolve the situation where two different keys hash to the same bucket index. Collisions are inevitable...
Separate Chaining
Collision handling is the set of techniques used to resolve the situation where two different keys hash to the same bucket index. Collisions are inevitable in any hash table that stores more than one element, because the number of possible keys is vastly larger than the number of buckets. Two broad strategies exist: separate chaining and open addressing.
Separate chaining resolves collisions by storing all elements that hash to the same bucket in a linked list (or other dynamic structure) attached to that bucket. The bucket array holds pointers to the heads of these chains. When a collision occurs, the new element is simply appended to the chain at the relevant bucket.
Lookup with chaining: compute the bucket index, then scan the chain at that bucket comparing each key to the target until a match is found or the chain is exhausted.
Average chain length equals n divided by m, where n is the number of entries and m is the number of buckets. At a load factor of 0.75, the average chain length is 0.75, and lookups require on average 1.75 comparisons (one to check the bucket is non-empty, 0.75 on average to scan the chain). This keeps performance close to O(1).
Separate chaining tolerates load factors greater than 1, meaning more entries than buckets, without catastrophic performance degradation. Performance degrades linearly with the load factor. At a load factor of 3, the average chain length is 3, and lookups average 3 comparisons. This is still fast in absolute terms.
A variation replaces linked lists with balanced trees for the chains. Java's HashMap does this: when a chain's length exceeds 8, it converts the chain from a linked list to a red-black tree, reducing worst-case lookup within the chain from O(n) to O(log n). This protects against adversarial inputs that would otherwise create O(n) chains.
A worked example: with m equals 7 buckets and n equals 10 keys, by the pigeonhole principle at least 3 buckets must be empty and at least one bucket must hold at least 2 entries. With a good hash function, the load is approximately 1.43 per bucket on average.
Interview tip: mention that Java HashMap converts chains to trees at length 8 as a defense against worst-case attacks. This specific detail demonstrates familiarity with production-quality hash table implementations.
Open Addressing
Open addressing is an alternative collision resolution strategy where all entries are stored directly in the bucket array itself, with no pointers or auxiliary data structures. When a collision occurs, the algorithm probes a sequence of alternative bucket positions until it finds an empty slot.
The three main probing strategies are linear probing, quadratic probing, and double hashing.
Linear probing places the key at the next empty slot in order: if bucket h is occupied, try h+1, then h+2, and so on, wrapping around. This is cache-friendly because probed buckets are adjacent in memory, but it creates primary clustering: long runs of occupied buckets that cause new insertions to probe many slots.
Quadratic probing uses a quadratic function of the probe number: if h is occupied, try h plus 1 squared, then h plus 2 squared, then h plus 3 squared. This reduces primary clustering but introduces secondary clustering: all keys that hash to the same initial bucket follow the same probe sequence.
Double hashing uses a second hash function to determine the step size: if h is occupied, try h plus k times step, where step is derived from the key using a different hash function. This eliminates both primary and secondary clustering, providing near-random probe sequences. Double hashing is the most collision-resistant probing strategy.
Deletion in open addressing requires care. Marking a slot as deleted (a tombstone) rather than empty is essential, because an empty slot terminates probing and a physical deletion would make subsequent lookups fail to find keys inserted after the deleted key.
A worked example: inserting keys that hash to bucket 3 with linear probing into a 7-slot table. First key goes to slot 3. Second key goes to slot 4. Third key goes to slot 5. A lookup for a key hashing to slot 3 probes 3, then 4, then 5 before finding the target or an empty slot.
Time complexity: O(1) expected for all operations with a good hash function and load factor below 0.7. Space complexity: O(m) for the table, no auxiliary structures.
Interview tip: recommend linear probing for cache-friendly practical performance when the load factor stays below 0.5, and double hashing when load factors must approach 0.8 or when adversarial inputs are a concern.
Comparing Chaining and Open Addressing
The choice between separate chaining and open addressing has significant practical implications for performance, memory use, and implementation complexity. Understanding the trade-offs helps you make informed decisions in both interviews and production systems.
Memory layout is the most fundamental difference. Open addressing stores all data in a contiguous array, which is cache-friendly. When probing for a key, the CPU loads nearby memory into cache, and subsequent probes often hit data already in cache. Separate chaining stores chain nodes as heap-allocated objects scattered throughout memory. Following a pointer to the next chain node often causes a cache miss.
This cache advantage makes open addressing faster in practice at low to moderate load factors (below 0.7). Benchmark studies consistently show that linear probing outperforms chaining for load factors below 0.5 by a factor of 2 to 3 in throughput on modern hardware.
At high load factors, separate chaining is more robust. Open addressing degrades sharply as the load factor approaches 1.0 because the average probe length grows without bound: for linear probing, the expected number of probes for a successful lookup is approximately 1 plus 1 divided by (1 minus load_factor) squared divided by 2. At a load factor of 0.9, this is approximately 5.5 probes per lookup. Separate chaining at the same load factor averages 1.45 probes, a nearly four-fold advantage.
Memory overhead also differs. Separate chaining needs pointers in each node (8 bytes per pointer on a 64-bit system) plus the overhead of the memory allocator. Open addressing needs extra empty slots to maintain performance, typically reserving 25 to 50 percent of the array.
A worked example showing the practical impact: a read-heavy hash table in a game engine that maps string identifiers to asset pointers at a load factor of 0.5 should use open addressing with linear probing. The cache efficiency provides a measurable frame-rate improvement over chaining in profiles.
Interview tip: when asked which collision strategy to use, ask about the load factor and access patterns. State that open addressing is faster at low load factors due to cache locality, while chaining is more predictable at high load factors. This context-driven answer impresses interviewers.