Hash Collisions
When two keys hash to the same bucket, a collision-resolution scheme keeps operations correct and fast; chaining and open addressing are the two families.
Collisions are inevitable
A hash function maps a large key space onto a small array, so distinct keys must sometimes share a bucket. By the pigeonhole principle collisions cannot be avoided; they can only be resolved. The birthday paradox makes them common even at modest load: with only a few dozen items in a hundred buckets, sharing is likely.
Separate chaining
Each bucket holds a container, usually a linked list, of all entries that hashed there. Insert prepends to the list; lookup walks it comparing keys. With a good hash and load factor near one, chains stay short and operations remain O(1) on average. Some implementations promote a long chain into a balanced tree to bound the worst case at O(log n).
Open addressing
Open addressing stores every entry directly in the array and, on collision, probes a sequence of alternative slots until a free one is found. Linear probing tries the next slot, which is cache-friendly but causes primary clustering. Quadratic probing and double hashing spread probes out to reduce clustering.
- Linear probing: slot, slot+1, slot+2, …
- Quadratic probing: slot, slot+1, slot+4, slot+9, …
- Double hashing: step size set by a second hash function
Deletion under open addressing
Deletion is subtle: simply emptying a slot would break probe chains that pass through it. The fix is a tombstone marker that says occupied-but-deleted, so probes continue past it while inserts may reuse it. Too many tombstones slow lookups and trigger a rehash.
Choosing a scheme
Chaining tolerates high load factors and simple deletion but scatters memory. Open addressing has better cache locality and no per-entry pointers but degrades sharply as the table fills and needs tombstones. Both keep expected O(1) operations when the load factor is controlled.