Marc Rasmussen Marc Rasmussen - 11 days ago 5
Java Question

Double hashing constant 5?

Ive found loads of examples of double hashing all of the examples tell me that you have to use %5 when you hash the 2nd time.

My question is why 5? is it an agreement that you always use 5 or how does it work?

one example: https://www.cs.washington.edu/education/courses/326/00wi/handouts/lecture16/sld025.htm

Answer

In a hash table with N places, the idea is to use two independent hash functions h1(key) and h2(key) and then use the probing sequence

h1 % N, (h1 + h2) % N, (h1 + 2*h2) % N, (h1 + 3*h2) % N, ...

You want to make sure that the the greatest common divisor of h2 and N is 1, otherwise you do not reach all places in the table.

there are several schemes this can be achieved, for example:

  • choose N as a prime and let h2 give a result in the interval [1, N-1]
  • choose N as a power of 2 and let h2 give an odd number in the interval [1, N-1]
Comments