Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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}$
