Math Genius: show that $h(k)=left lfloor{frac{k}{m}}right rfloor mod m$ is a bad hash function where $m$ is prime

Original Source Link

A “good” hash function should make use of all slots with equal frequency. In this case the ammount of slots is given with $m$.

Also keys which are similar should be distributed as broadly as possible.

Any ideas how to approach this excercise?

Hint. Take for instance $m = 5$ and consider the numbers $0, 1, ldots, 29$. Then you will have $10$ numbers in slot $0$, but only $5$ numbers in slots $1$, $2$, $3$, $4$. Thus taking $k bmod m$ would give a much better result.

Tagged : /

Leave a Reply

Your email address will not be published. Required fields are marked *