[TechSyndrome]

I'm looking at a lecture slide where I'm given an example of double hashing in a hash table:

I also have previous slides that explains this, but I'm having trouble understanding some of it. Here they are:





I managed to insert - 18, 41 and 22. But, when it comes to 44, I think the formula ends up as h(44) = 7 - 44 mod 7. Now does this mean I actually have to minus 7 from 44?

Edit: I arrived at 5, but I noticed in the slide that under probes (I'm not sure what that is), it displays 5 and 10, and that's represented in the table (the yellow one below).

This post has been edited by TechSyndrome: 12 August 2012 - 06:36 PM

[blackcompe]

For insert(44), you'd compute H(44) = 44 mod 13 = 5 and see that there's a collision. Then you'd double hash and compute H'(44) = 7 - 44 mod 7 = 5 mod 13 = 5. The final position is H + H' = 5 + 5 = 10 mod 13 = 10. If there were another collision (although there isn't one), you'd double hash again - H'(44) = 7 - 44 mod 7 = 5 mod 13 = 5 - and add that to the probe where the last collision occurred - 10 + 5 mod 13 = 2 mod 13 = 2.

Edit:

Quote

I arrived at 5, but I noticed in the slide that under probes (I'm not sure what that is), it displays 5 and 10, and that's represented in the table (the yellow one below).

"Probes" are the final positions where the element is placed in the array. The first time 44 is inserted, it goes into position 5 of the array, but if there's a collision, the hash is re-computed, where 10 becomes the next final position in the array, and so on. So the probes are 5 and 10.

This post has been edited by blackcompe: 12 August 2012 - 06:43 PM

[TechSyndrome]

blackcompe, on 12 August 2012 - 06:37 PM, said:

For insert(44), you'd compute H(44) = 44 mod 13 = 5 and see that there's a collision. Then you'd double hash and compute H'(44) = 7 - 44 mod 7 = 5 mod 13 = 5. The final position is H + H' = 5 + 5 = 10 mod 13 = 10. If there were another collision (although there isn't one), you'd double hash again - H'(44) = 7 - 44 mod 7 = 5 mod 13 = 5 - and add that to the *last* position where the collision occured - 10 + 5 mod 13 = 2 mod 13 = 2.

Edit:

Quote

I arrived at 5, but I noticed in the slide that under probes (I'm not sure what that is), it displays 5 and 10, and that's represented in the table (the yellow one below).

"Probes" are the final positions where the element is placed in the array. The first time 44 is inserted, it goes into position 5 of the array, but if there's a collision, the hash is re-computed, where 10 becomes the next final position in the array, and so on.

Thanks. When you say:

"For insert(44), you'd compute H(44) = 5 and see that there's a collision. Then you'd double hash and compute H'(44) = 7 - 44 % 7 = 5 mod 13 = 5" What actually happens here (the boxed area)?

In steps, is it:

1. 44 % 7 which equals 2, then 7 - 2 = 5, then go back to the original function (in this case % 13)
2. 5 % 13 = 5, then that result basically doubled?

This post has been edited by TechSyndrome: 12 August 2012 - 06:49 PM

[blackcompe]

Quote

"For insert(44), you'd compute H(44) = 5 and see that there's a collision. Then you'd double hash and compute H'(44) = 7 - 44 % 7 = 5 mod 13 = 5" What actually happens here (the boxed area)?

According to the definition of H', which is 7 - k mod 7, your steps exactly are:

1. H' = 7 - K mod 7 => 7 - 44 mod 7 => -37 mod 7 => 5

Here's what's happening on a conceptual level: Double hashing is an open-addressing scheme, where H' is used to compute the probe interval. Take linear probing for example, where if there's a collision, you just advance to the next open array index until you find an open space. The probe interval is simply 1. Therefore, the final position is H(k) + 1 if a collision occurs at H(k). In double hashing, the probe interval is H', and therefore the final position is H(k) + H'(k) if a collision occurs at H(k).

In either case, if a collision occurs a 2nd time after probing, you just repeat the process, where for linear probing the final position becomes H(k) + 1 + 1 and for double hashing the final position is H(k) + H'(k) + H'(k). And that concept extends for however many collisions you run into until you find an empty space. E.g. a third collision is H(k) + 3 for linear probing and H(k) + 3H'(k) for double hashing.

Trying to find an empty space is essentially what "probing" is. Each probe is the array index that you try to insert the key into, regardless of whether there's a collision or not. A probe sequence is the list of probes that were tried until you found a resting place. So for insert(44), the probe sequence is 5, 10. You collided at 5 (since 18 was there) and you succeeded at 10.

Finally, you have - insert(44) = H(k) + H'(k) - since H(k) produces a collision. H(k) + H'(k) = 5 + 5 = 10.

You might consider double hashing over linear probing when the table is small (where cache performance won't be a problem) and you want a nice even distribution of the keys (no clustering), which should decrease the time it takes to do lookups and insertions.

This post has been edited by blackcompe: 12 August 2012 - 10:59 PM