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



Designing a Hash function that results in minimum size and no collisions 
Have a look at [Perfect Hash Functions](http://en.wikipedia.org/wiki/Perfect_hash_function), especially the discussion on *minimal perfect hash functions*


