c++data-structureshashhashtabledouble-hashing

How the Double Hash Function Works in C++?


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.

enter image description here

Now confusion starts. as they are saying in image. 49 should be on 7 positions from [9] index. then the actual position will be [6] then why they placed 49 at [0] index? and same for other remaining integer.

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


Solution

  • 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.