Double hashing constant 5? [closed]

Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 8 years ago.

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 1

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]

Answer 2

No. The second hashing function can be whatever you want it to be. Ideally, it should have an equal chance of reaching every cell of your hash array.

My guess is you didn't look up any examples for double hashing from a different source. The source you used decided to use % 5 multiple times for simplicity.

Answer 3

You don't always use 5, and you even don't always use % either.

In your example. %7 and %5 are your hashing functions. However, in reality, they could be completely different functions.

This example uses %5 because it is simple enough for the example. The only real requirement is that the two functions are independent.

See http://en.wikipedia.org/wiki/Double_hashing.