I'm practicing an exam for a data structures course. There's a question about a hash table with hash function: $$h'(k,i)=h_1(k)+i*h_2(k) \mod{11}$$ where $$h_1(k)=k \mod{13}$$ and $$h_2(k) = 1 + k \mod{7}$$

There's a question: What problem will occur if we change the table size to 12 and we also change the module in $$h'(k,i)$$ to 12?

I thought that the new hash function outputs 0 on some occasions, although I don't really see why would it be any worse than 11, which would also output 0 sometimes.

  • 3
    $\begingroup$ Hint: investigate the distribution of elements. Note that in the setup, all three divisors are prime (before the change). $\endgroup$ – Raphael Jun 22 '15 at 15:42
  • $\begingroup$ What is your goal? Without a clear goal, any hash function is "good enough", even the one that gives 0 on any input. $\endgroup$ – Ran G. Jun 23 '15 at 0:23
  • $\begingroup$ The goal is to avoid collisions as much as possible, and evenly fill the table. I already got that those numbers are prime, but that doesn't help me much. $\endgroup$ – riccardo_92 Jun 23 '15 at 14:14
  • $\begingroup$ Could you edit your question to contain all the needed information in a clear and formal way? $\endgroup$ – Ran G. Jun 23 '15 at 16:23
  • $\begingroup$ @Raphael how would you go about finding out the distribution? If I do for i in range(200): (i %13) % 7 it gives a linear sequence which shows that it doesn't matter what you mod with. What sequence would you use to show the performance of this hash in terms of collision rate? $\endgroup$ – user1932405 Jul 8 '15 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.