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

Question

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?

Answer 1

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$.