data-structureshashhashtabledouble-hashing

What should I do if double hashing function also failed

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.

Solution

  • 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