2
$\begingroup$

For double hashing, we have some constraints on $h'(k)$

(1) It should never evaluate to 0

(2) It should be relatively prime to m

How to show that all slots in an open addressing table will be included in a probe sequence.

$\endgroup$
2
$\begingroup$

In double hashing, we have (for a specific $k$) the series $h(k) + nh'(k) \mod m$

Since we have that $gcd(h'(k), m) = 1$ (they are relatively prime), then from Bézout's identity there exists two integers a,b such that $ah'(k) + bm = 1$. since $h'(k)$ is not 0, we can conclude that b is not 0 and thus also a is not 0. We have $ah'(k) = 1 \mod m$, which means that a is the inverse of h'(k) in modulo m.

Now, let $0 \leq i \leq m$ be an integer. by choosing $n = ia$, we have $( h(k) + nh'(k) ) \mod m = ( h(k) + iah'(k) ) \mod m = ( h(k) + i ) \mod m$.

This concludes the proof (think why).

I hope i managed to help!

$\endgroup$
1
$\begingroup$

Answer to 2nd part

In double hashing, let the hash function be h(k, i) where k is the key and i is the probe sequence.

Let h(k, i) = h(k, j) for some i and j where j > i. This means that starting at ith step, after (j-i) more steps, the hash function points to the same slot. Let m be the size of the table. Also, h1(k) and h2(k) are ordinary hash functions.

h(k,i) = h(k, j)
(h1(k) + i * h2(k)) mod m = (h1(k) + j * h2(k)) mod m
(i * h2(k)) mod m = (j * h2(k)) mod m
((j - i) * h2(k)) mod m = 0

Since, h2(k) and m are relatively prime, therefore (j - i) must be a multiple or at least m. Therefore, for the hashing function to repeat the slot, the steps must be at least m.

This proves that keeping h2(k) and m relatively prime, the double hashing hits all slot in a table of size m producing all permutations of m.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.