Compare four collision resolution techniques for hash tables: separate chaining, linear probing, quadratic probing, and double hashing — analyzing their performance, clustering behavior, and practical trade-offs.
| Technique | Best Case | Average Case | Worst Case | Clustering | Deletion |
|---|---|---|---|---|---|
| Separate Chaining | O(1) | O(1) | O(n) | None | Easy |
| Linear Probing | O(1) | O(1) | O(n) | Primary clustering | Tombstones |
| Quadratic Probing | O(1) | O(1) | O(n) | Secondary clustering | Tombstones |
| Double Hashing | O(1) | O(1) | O(n) | Minimal | Tombstones |
- Separate chaining is simplest — each slot has a linked list; performance depends on chain length (load factor α)
- Linear probing causes primary clustering — long runs of occupied slots form, increasing probe lengths
- Quadratic probing reduces primary clustering but causes secondary clustering (same initial hash = same probe sequence)
- Double hashing is best — different step size per key eliminates most clustering, probes all slots if table size is prime
- Load factor α ≤ 0.7 is critical — all methods degrade rapidly above this threshold
- Open addressing (probing) uses less memory (no linked list pointers) but requires more careful load factor management
The choice depends on use case: separate chaining for simplicity and easy deletion; double hashing for best theoretical performance; linear probing only for very low load factors. All methods require good hash functions and load factor monitoring.
- Hashing — the fundamental technique
- Separate Chaining — linked lists at each slot
- Linear Probing — probe next slot
- Quadratic Probing — probe with i² skip
- Double Hashing — two hash functions
- Load Factor — critical for all methods
- Hash Function — quality affects all methods