Double Hashing
Double hashing improves on linear probing:
- by using an increment which ...
- is based on a secondary hash of the key
- ensures that all elements are visited
(can be ensured by using an increment which is relatively prime to N)
- tends to eliminate clusters ⇒ shorter probe paths
To generate relatively prime
- set table size to prime e.g. N=127
-
hash2() in range [1..N1] where N1 < 127 and prime
|