1
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Aug 16, 2012 at 21:06

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .