# Double hashing constraints

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.

## 2 Answers

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.