UnKnown - 4 months ago 29

C++ Question

I was reading about HashTable and found a good source to easily understand Here.

But I got confused on double hashing function. Here is the detail of double hashing function.

Double hashing uses the idea of applying a second hash function to the

key when a collision occurs. The result of the second hash function

will be the number of positions form the point of collision to insert.

There are a couple of requirements for the second function:

`it must never evaluate to 0`

must make sure that all cells can be probed

A popular second hash function is: Hash2(key) = R - ( key % R ) where

R is a prime number that is smaller than the size of the table.

and Here is the Image of double hash function.

Now confusion starts. as they are saying in image. 49 should be on

`7`

`[9]`

`[6]`

`[0]`

And what will happen when there will be no empty index?

Answer

Indeed image is **wrong**. Basic idea is to jump by no of places by value given by second has function, if already occupied, then keep jumping by same no. of places till an empty cell is found. For this to work, second hash function must NOT return 0.

For more explanation please see here.