javahashdouble-hashing

Confusing about calculating the probe sequence in double hashing


I know that in Double Hashing,

h1(key) = key mod 11
h2(key) = 7 - (key mod 7)

The h1 represents starting at location h1(key), h2 represents the size of the step taken.

But I do not know how to solve for the probe sequence.

For example, if key is 14.

Can you explain to me why the answer is 3,10,6,2,9,5,1,8,4,0.


Solution

  • In your example, the size of the table is 11 (positions numbered 0 to 10). The size of the step is the number to add to the current position to get the next position (modulus the size of the table).

    h1 = 14 mod 11 = 3
    h2 = 7 - (14 mod 7) = 7 - 0 = 7
    

    So, the first position, call it p, is 3, as given by h1. Each subsequent position, p' is given by --

    p' = (p + h2) mod table_size
    

    for this example,

    p' = (p + 7) mod 11
    

    so, the second position is --

    (3 + 7) mod 11 = 10 mod 11 = 10
    

    and the third is --

    (10 + 7) mod 11 = 17 mod 11 = 6
    

    and so on.