0
$\begingroup$

I am trying to create a special purpose hash function that will have as few collisions as possible.

$99\%$ of the input will be sequential numbers, from $1$ to $N$. The size of the hash table will be $\frac{N}{10}$.

Can anyone provide the perfect hash function for this input?

$\endgroup$
1
$\begingroup$

If perfect means as few collisions as possible, you can just do $f(n)=(n \pmod N)/10$ where the divide is integer division. You have to have $10$ of each number in the range $[1,N]$ mapped to each hash value, which this does.

Often we also ask that hash functions be such that one cannot reasonably predict the hash from the number to be hashed, nor invert it to find a number that will match a given hash. If you want that as well, just take any current cryptographic hash function (which will presumably return a number much larger than $\frac N{10}$), then take the output $\bmod \frac N{10}$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.