# Why we get at most $N^2$ probe sequences using double hash function

Question:Given the following double hash function:

$$h(k,i) = (h_1(k) + i\times h_2(k)) \bmod{N}$$, where $$h_1(k): key \to \mathbb{Z}$$. $$h(k,i)$$ can generate $$N^2$$ probe sequences at most and $$h_2(k)$$ can determine the increment for the probe sequence. Also, $$N$$ is the number of slots.

Problem:Each sequence generated from double hash function regarded as 1 of $$N^2$$, so my question is why at most we can have $$N^2$$ probe sequences please? For example, in linear hashing where $$h(k,i) = (h_1(k) + i) \bmod{N}$$ , we can have N probe sequences at most because for each number $$i=0,1, \cdots$$ we can get a sequence. Similarly, why we get $$N^2$$ probe sequences in the double form please?

Note that $$(h_{1}(k))\mod N$$ can take $$N$$ distinct values and $$(h_{2}(k))\mod N$$ can take $$N$$ distinct values. To show that the total number of sequences are $$N^2$$, we will need to show that for some different inputs $$k_1$$ and $$k_2$$, if $$(h_{1}(k_{1}) \not\equiv h_{1}(k_2) \mod N)$$ or $$(h_{2}(k_1) \not\equiv h_2(k_2) \mod N)$$, then the probing sequences would be different for $$k_1$$ and $$k_2$$. Let the sequence generated by $$k_1$$ is $$P_1$$ and the sequence generated by $$k_2$$ is $$P_2$$.

Proof: Suppose $$(h_{1}(k_{1}) \not\equiv h_{1}(k_2) \mod N)$$. Then, for $$i = 0$$, the first element of the $$P_1$$ would be $$h_{1}(k_{1}) \mod N$$, and the first element of the $$P_2$$ would be $$h_{1}(k_{2}) \mod N$$. Since their first elements are different, the sequences are different.

And, suppose if $$(h_{1}(k_{1}) \equiv h_{1}(k_2) \mod N)$$ and $$(h_{2}(k_{1}) \not\equiv h_{2}(k_2) \mod N)$$. Then, for $$i = 1$$, the second element of $$P_1$$ would be $$(h_{1}(k_{1}) + h_{2}(k_{1})) \mod N$$ which is different from the second element of $$P_2$$, i.e., $$(h_{1}(k_{2}) + h_{2}(k_{2})) \mod N$$. You can easily prove this statement using contradiction.

Note: I noticed later that you are just asking for at most $$N^2$$ sequences. It is actually trivial since $$(h_{1}(k)\mod N)$$ can take $$N$$ distinct values and $$(h_{2}(k)\mod N)$$ can take $$N$$ distinct values. For a fixed value of $$(h_{1}(k)\mod N)$$ and $$(h_{2}(k)\mod N)$$, we have a particular sequence. Therefore, the sequences can be at most $$N^2$$. But, what I proved earlier is much stronger, i.e., the number of possible sequences could actually be $$N^2$$.

• @Avra I mean that $(h_1(k_1) \mod N) \neq (h_1(k_2) \mod N)$. Does that clarify? Maybe I should say $h_1(k_1) \not\equiv h_1(k_2) \mod N$... Aug 28 at 18:47
• @Avra Yes. For a fixed value of $(h_1 \mod N)$ and $(h_2 \mod N)$, there is one particular sequence. So, in total, we would have $N$ different values for each from first hash function $(h_1 \mod N)$ and similarily for $(h_2 \mod N)$, which gives in total $N^2$ sequences. Aug 28 at 18:54