# Designing a Hash function that results in minimum size and no collisions

Dear all,

I have the following problem: Consider an array of $N$ vectors $v_{i} \ i=1...N$ of size $L$ bits, where each bit is 1/0 with equal probability. I want to find a hash function $H()$ that results in no collisions when hashing the N vectors, i.e. $H(v_{i}) \neq H(v_{j}) \ \forall i \neq j$, and such that the maximum value of the hash is as small as possible, i.e. $\max{H(v_{i})} \forall i$ is minimized.

My first approach to the problem (without any formal ground) is the following:

1- Let $d_{i}$ be the decimal representation of $v_{i}$.

2- Define as hash function $H(v_{i}) = H(d_{i}) = d_{i} \mod K$.

3- Then, find the smallest $K$ such that there are no collisions between the vectors.

4- In order to do the above I simply have an iterative algorithm that starts with $K_{0} = N$, and increases $K$ by one until it finds a $K$ that results in no collisions.

Does anyone have a suggestion on how to find a better solution for the previous problem? A better solution is ideally one that results in no collisions and achieves a smaller $\max{H(v_{i})} \forall i$, or one that achieves the same $\max{H(v_{i})} \forall i$ but can be implemented with a more efficient algorithm that the one I just described.

Thanks a lot

Daniel

-
If you are unfortunate enough to be given 0 and the numbers from N+1 to 2N-1, it will take your scheme a while to find the desired modulus. We can extend this by using products like (N+i)(2N+i) for many i, and so on. You might find it useful to study examples like this in your research. Gerhard "Ask Me About System Design" Paseman, 2012.08.16 – Gerhard Paseman Aug 16 '12 at 21:06