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

Question

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.

Answer 1

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:

• Double Hashing in Wikipedia
• Double Hashing Example
• Hashing - Double Hashing Collision Resolution

Bonus:

• What is the Best Second Hash function when using Double Hashing?

Answer 2

In double hashing, you repeat the 2nd hash step until a free spot is found. The process is to keep adding H2(k) to the last index (modulo size) to generate the next index.

In your example, this translates to:

H1(9) = 9 % 8 = 1
H2(9) = 7 - (9 % 7) = 5

Attempted spots: 1, 6, 3, 0, 5, 2, 7, 4

So the 9 value would be stored at index 3.