Search code examples
hashhashtabledouble-hashing

What if a collision still exists after applying the double hashing algorithm?

I have a hash table of size 8 where I want to insert the values (0, 1, 8, 9, 5, 33).
I tried it with hashing which has collision then I tried the double hashing algorithm but the collision still occurs as follows:

Hashing = H1(k) = k % 8
Double Hashing = H2(k) = M - (k % M)

H1(0) = 0 % 8 = 0   
H1(1) = 1 % 8 = 1  
H1(8) = 8 % 8 = 0 -----> Needs double hashing ----> 7-(8 % 7)=7-1=6 (we forward 6 steps from the current position which is 0 and it will become 6).  
H1(9) = 9 % 8 = 1----> Needs double hashing ---> 7 - (9%7)=7-2=5(we forward 5 steps from the current position which is 1 and it will become 6 again).

Now I am stuck here and I dont know what to do. Note: I do not want to use any other method, I want to use only double hashing.
Any help is appreciated in advance.

Solution

  • You must use the double hashing algorithm as intended.

    As mentioned in this very nice article:

    Double hashing can be done using : 

    (hash1(key) + i * hash2(key)) % TABLE_SIZE

    Here hash1() and hash2() are hash functions and TABLE_SIZE is the size of hash table. (We repeat by increasing i when a collision occurs)

    And the given example is (in your case):

    H1(0) = 0 % 8 = 0   
H1(1) = 1 % 8 = 1  
H1(8) = 8 % 8 = 0
   H2(8) = 7 - (8 % 7)= 7-1 = 6
   // double hashing algorithm start : i == 1
   (H1(8) + i*H2(8)) % TABLE_SIZE = (0 + 1*6) % 8 = 6       

H1(9) = 9 % 8 = 1
   H2(9) = 7 - (9 % 7)= 7-2 = 5
   // double hashing algorithm start : i == 1
   (H1(9) + i*H2(9)) % TABLE_SIZE = (1 + 1*5) % 8 = 6 --> collision (increment i to 2)
   (H1(9) + i*H2(9)) % TABLE_SIZE = (1 + 2*5) % 8 = 3 --> no collision

    Additional References:

    Bonus: