### double hashing

i found this example on internet :
h1(K) = K mod 13
h2(K) = 8 - K mod 8
insert 18 41 22 44 59 32 31 73 into 13 - item hash table
0 : 44
1 :
2 : 41
3 : 73
4 :
5 : 18
6 : 32
7 : 59
8 : 31
9 : 22
10 :
11 :
12 :

i understand the numbers that are not overlap, but with some overlap numbers, i just dont understand their places in hash table
Ex : with 44, when K = 44 => h1(44) = 5 overlap with 18
so i start to compute h2(44) = 4 but they place 44 at position 0 while the position 4 is empty, why?
and what should i do if h2(K) is overlap too
thanks so much everybody
You seem to have copied this example from a presentation I googled. The explanation is given two slides before the example:

 1234567 double_hash_insert(K) if(table is full) error probe = h1(K) offset = h2(K) while (table[probe] occupied) probe = (probe + offset) mod M table[probe] = K

So it tries positions 5 (occupied), 5+4 (occupied), 5 + 4 + 4 (mod 13) -> 0 (free) -> put the value there.
Last edited on
Thanks, you saved me , KRAkatau, now i understand
Last edited on
Topic archived. No new replies allowed.