Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

Have a look at Perfect Hash Functions, especially the discussion on minimal perfect hash functions

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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