Double Hashing - HashValues outside of HashTable Range

Question

I have here a homework about double hashing and I stack on one point:

I have the Array: 17, 6, 5, 8, 11, 28, 14, 15 h1(k) = k mod 11, h2(k) = 1 + (k mod 9), Size of hash table = 11 The double Hash Function from this: dh(k) = k mod 11 + (j + (k mod 9).

Now I calculate the hashvalues:

h(17) = k mod 11 = 6 - OK
h( 6) = 6 = collision => 6 + (1 + (6 mod 9) = 12 = NOK 

=> this is outside of the range of my Indices, and with every higher Index number it also will be higher. If I change the addition of the second HashFuncion into a subtraction, then the HashValues will get into negatives - what also is not good.

What am I doing wrong?

Thanks Zuzana

Answer 1

I think you're misinterpreting how to compute the index for a double hash. The index should be

(h₁(k) + j · h₂(k)) mod TableSize

So the formula you should use with those two hash functions would be

((k mod 11) + j · (1 + (k mod 9))) mod 11