[prev] [index] [next]

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