What should I do if double hashing function also failed

Question

Consider inserting the keys 10, 22, 31, 9 , 15, 28, 62, 88 in to a hash table of length m = 11 using open addressing with the hash function h(k) = k mod m. Illustrate the result of inserting these keys using double hashing with h2(k) = 1 + (k mod(m-1)).

Following is my approach.

0 -> 22 , Since 22 mod 11 = 0
1 ->
2 ->
3 ->
4 ->
5 ->
6 ->
7 ->
8 ->
9 -> 31 , Since 31 mod 11 = 9
10 -> 10 , Since 10 mod 11 = 10

Ok the problem comes when try to put the key 9 in to the hash table.

h(9) = 9 mod 11, which is 9. I can't put 9 since 9 already gone. Then I try for the double hash function given h2(9) = 1 + (9 mod (11-1)) , which is 10 and it's gone again. So still I can't put 9 in to the hash table. What should I do in such scenarios.

Answer 1

Finally I could find the answer using wiki explanation. http://en.wikipedia.org/wiki/Double_hashing

h(9) = 9 mod 11, which is 9.

h2(9) = 1 + (9 mod (11-1)) which is 10.

So the key has should be (9 + 10) mod 11 which is 8.

then

8 -> 9

Answer 2

Use the two hash function like this:

hi=(h(key)+i*h1(key))％m 0≤i≤m-1

In other words: you increment with the value of the second hash function h1 each time, wrapping around as necessary.

So the addresses list you would look for a key is as follows:

h(key), h(key)+h1(key), h(key)+2*h1(key), ... , h(key)+n*h1(key)