Quadratic probing still has secondary clustering (keys with same initial hash follow same probe sequence). We need a way to give each key a unique probe sequence.
Double hashing uses two hash functions: the second hash determines the step size for probing, giving each key a unique probe sequence.
- Compute h₁(k) = initial position
- Compute h₂(k) = step size (must be non-zero)
- Probe sequence: h₁(k), h₁(k)+h₂(k), h₁(k)+2h₂(k), …
- Each key has different step size → different probe sequence
- Best open addressing method (least clustering)
- Probes all slots if table size is prime and h₂(k) is non-zero
- More computation (two hash functions)
- Step size must be non-zero and relatively prime to table size
- Built from: Hashing, Hash Function
- Builds into: Collision Resolution
- Related: Linear Probing, Quadratic Probing
- Contrasts with: Quadratic Probing (two hashes vs one quadratic)
- h₂(k) must never be 0 (would infinite loop)
- Table size should be prime for complete coverage
- Most complex to implement of the three probing methods