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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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!
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.