Collision resolution
Every hash table needs a strategy for keys that land in the same bucket. The two main families are chaining and open addressing.
Separate chaining
In separate chaining, each bucket holds a small list of all items that hash there. Insert adds to the bucket's list; lookup and delete scan only that list. If n items are spread over m buckets, the average list length is the load factor alpha = n / m, so operations cost O(1 + alpha) on average. Chains can grow without limit, so the table never becomes full.
Open addressing
Open addressing stores all items directly in the array. On a collision, the table probes a sequence of other slots until it finds an empty one. Lookup follows the same probe sequence until it finds the key or an empty slot. There are no pointers, which saves memory and improves cache behaviour, but the load factor must stay below 1.
Linear probing
Linear probing tries h(k), h(k) + 1, h(k) + 2, and so on, wrapping around. It is simple and cache-friendly, since probes touch adjacent slots, but suffers from primary clustering: runs of occupied slots grow and merge, so keys landing anywhere in a run must walk to its end. It performs well when the load factor stays moderate, say below 0.7.
Quadratic probing and double hashing
Quadratic probing tries h(k) + 1, h(k) + 4, h(k) + 9, and so on, which breaks up primary clusters, though keys with the same starting slot still follow the same path: secondary clustering. Double hashing uses a second hash function for the step size, h(k) + i x h2(k), so different keys follow different sequences, approximating ideal uniform probing.
Deletion in open addressing
Simply emptying a slot breaks lookups for keys that were placed after probing past it, because a search would stop at the new gap. Instead, deleted slots are marked with a tombstone: lookups skip over tombstones, and insertions may reuse them. Many tombstones degrade performance, so tables are periodically rebuilt.
Expected costs
With uniform hashing and load factor alpha below 1, an unsuccessful search in open addressing probes on average about 1 / (1 - alpha) slots: 2 at alpha = 0.5, 10 at alpha = 0.9. Performance therefore collapses as the table fills, which is why open-addressing tables resize well before they are full.
Modern designs
Real libraries blend these ideas. Python's dict uses open addressing with a perturbed probe sequence and a compact layout that preserves insertion order. Java's HashMap uses chaining, converting a bucket's list to a red-black tree when it exceeds 8 entries. Robin Hood hashing and Swiss tables, used in fast C++ and Rust libraries, reduce probe-length variance and use processor vector instructions to check many slots at once.
Worked example
Table size 7, h(k) = k mod 7, linear probing. Insert 10: slot 3. Insert 17: 17 mod 7 = 3, occupied, try 4: placed. Insert 24: 3 taken, 4 taken, 5: placed. Insert 4: slot 4 taken, 5 taken, 6: placed. A cluster now fills slots 3 to 6, so a new key hashing to 3 must probe 5 slots. With chaining, bucket 3 would hold 10, 17, 24 and bucket 4 would hold 4.
Key takeaways
Chaining keeps a list per bucket; operations cost O(1 + alpha), and the table never fills. Open addressing probes for empty slots within the array, needing alpha below 1. Linear probing is cache-friendly but clusters; quadratic probing reduces clustering; double hashing gives key-specific step sizes. Deletion in open addressing uses tombstones. Unsuccessful searches cost about 1 / (1 - alpha) probes, so keep load moderate. Python's dict uses open addressing; Java's HashMap chains, switching long chains to trees; Swiss tables and Robin Hood hashing push performance further.
Flashcard
Each bucket holds a list of items
Check your understanding
In an open-addressing table, why can't you simply empty a slot when deleting a key?