# What is the best of given hashfunctions?

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.

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.