1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ @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$... $\endgroup$ Aug 28 at 18:47
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 28 at 18:54
  • 1
    $\begingroup$ 100% clear answer. $\endgroup$
    – Avv
    Aug 28 at 18:56
  • 1
    $\begingroup$ @Avra In case 2, the second element of the two sequences are different. Therefore, the sequences are different. Are you asking for its proof using contradiction? $\endgroup$ Aug 28 at 19:26
  • 1
    $\begingroup$ We can do it using contrapositive, so I am good at this point thanks. $\endgroup$
    – Avv
    Aug 28 at 19:30

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.