I am learning about Hashing and have struggles with the following assignment:

$U$ is a universe of keys with $Z(m)=\{0,\ldots, m-1 \}$ the amount of possible hash-values.

Given $U= \mathbb{Z}_{55} = \{0, \ldots, 54 \}$ and $m=5$.

Does the function $h(k,i)= (k+i) \bmod{5}$ fulfill the conditions for Uniform Hashing?

Uniform Hashing should be given when the probability that to a random key, a specific probe sequence trough the hash function is assigned, is $1/m!$ for all possible probe sequences... But I don't know how to proceed with checking whether this is given for the function above.

Any help and suggestions would be appreciated! :)

  • 3
    $\begingroup$ What have you tried? Where did it go wrong? Do you have an example of a proof or disproof of uniform hashing that you do understand? If not, that is a good place to start. $\endgroup$ – jbapple Feb 5 '17 at 19:28
  • $\begingroup$ Well, I guess I have to give it more thought... I do think that I understand why linear probing and quadratic probing are not good approxmations to uniform hashing, following the explanations found here (p.5): mi.fu-berlin.de/wiki/pub/ABI/AnalysisMethods/… $\endgroup$ – SimonAda Feb 6 '17 at 20:12

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.