372 views
0 votes
0 votes
Suppose that we use double hashing to resolve collisions--that is, we use the hash function $h(k,i) = (h_1(k) + ih_2(k))$ $mod$ $m$.Show that if $m$ and $h_2(k)$ have greatest common divisor $d\geq 1$ for some key $k$,then an unsuccessful search for key $k$ examines $(1/d)th$ of the hash table before returning to slot $h_1(k)$.Thus, when $d=1$, so that $m$ and $h_2(k)$ are relatively prime, the search may examine the entire hash table.

1 Answer

0 votes
0 votes
  1. Start with the double hashing probing formula:

    • h(k, i) = (h1(k) + i * h2(k)) % m
  2. We want to find out when the probe wraps around to the primary slot h1(k) after i steps. To do this, we need to find the smallest positive integer i such that:

    • (h1(k) + i * h2(k)) % m = h1(k)
  3. Simplify the equation:

    • (h1(k) + i * h2(k)) % m = h1(k)
    • Subtract h1(k) from both sides:
    • i * h2(k) % m = 0
  4. Now, we need to find the smallest positive integer i such that i * h2(k) is a multiple of m.

  5. Since d is the GCD of h2(k) and m, we can express h2(k) as d * h2'(k) and m as d * m', where h2'(k) and m' are integers:

    • h2(k) = d * h2'(k)
    • m = d * m'
  6. Now, the equation becomes:

    • i * (d * h2'(k)) % (d * m') = 0
  7. Divide both sides by d:

    • i * h2'(k) % m' = 0
  8. Now, we have the equation in terms of m':

    • i * h2'(k) % m' = 0
  9. The smallest positive integer i that satisfies this equation is i = m', because i needs to be a multiple of m' to make the remainder 0.

  10. Finally, since m' is the number of slots in the table (excluding the factor d due to GCD), the number of slots examined before wrapping around to the primary slot h1(k) is m'. Since m = d * m', the total number of slots in the table is m, and the number of slots examined is (1/d) * m, which means it's (1/d)th of the total number of slots in the table.

So, when h2(k) and m both have a GCD d >= 1, the number of slots examined in double hashing is indeed (1/d)th of the total number of slots in the table.

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
2
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Apr 4, 2019
232 views
Write pseudo code for $HASH-DELETE$ as outlined in the text, and modify $HASHINSERT$ to handle the special value $DELETED.$
0 votes
0 votes
0 answers
4