0
$\begingroup$

In our exam on algorithms there was a question, where given 3 hashfunctions we had to chose one and explain why it's the best.

h_1(x,i)=(x+5*i) mod 1000
h_2(x,i)=(x+17*i) mod 1000
h_3(x,i)=(x+32*i) mod 1000

I am really unsure about this, but I suspect that it is the second one, because it can "hit" more values. If I choose the first one for example, I will be hitting the same buckets over and over (if they are full). Question seems quite simple but my math lecture on this has been a long time ago.

$\endgroup$
1
$\begingroup$

The question is not well-defined, since its unclear what you mean by "best".

I suspect that the intended answer is what you said and that you are using open addressing. Then, for a given $x$, $h_2$ would eventually return all possible values in $\{0, \dots, 999\}$ (since $17$ and $1000$ are coprime). $h_1$ would only return $\frac{1000}{5} = 200$ distinct values, and $h_3$ would only return $\frac{1000}{\textrm{gcd}(32,1000)} = \frac{1000}{8}=125$ distinct values.

$\endgroup$
1
  • $\begingroup$ You suspected right. Thank you, this is what I wanted to hear :) $\endgroup$ Mar 13 '20 at 19:55

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.