1
$\begingroup$

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.

$\endgroup$
6
  • 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, 2015 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, 2015 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$ Jun 23, 2015 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, 2015 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$ Jul 8, 2015 at 13:55

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.