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