2
$\begingroup$

My understanding is that one way to build a perfect hash, as per CLRS, is to use two levels of hashing, with universal hashing functions at each level.

More specifically, CLRS shows that assuming $n$ is the total number of keys, and $n_j$ the number of keys hashed to the value $j$ for the second level, we can then make $m=n$ and $m_j=n_j^2$ to guarantee that the expected number of collisions is < 1/2 in the second level.

However, as far as I understand, collisions are still possible in this second level, so to truly have no collisions in this 2nd level, one may need to try a few hash functions in this level for each value of $j$.

Is my understanding correct? If so, CLRS does not seem to elaborate much on this algorithm. Is it fair to assume that a simple sequence of random "try and error" (i.i.d sampling) of hash functions (in this 2nd level) is "as good as it gets" at least for this perfect hashing design?

$\endgroup$
2
$\begingroup$

As mentioned by the OP in the comments, CLRS is using the ideas of Fredman, Komlós and Szemerédi, Storing a Sparse Table with $O(1)$ Worst Case Access Time.

Corollary 4 gives a range of parameters for which the construction succeeds with probability $1/2$; this could be amplified to any constant with minimal loss of parameters.

Lemma 2 shows how to derandomize the construction, but the resulting algorithm isn't practical.

You can also probably choose parameters for which the construction succeeds with high probability, in which case you can try your luck and not even check the hash function.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Worth noting that total construction time described seems to be polynomial: $O(n^3 \log m)$ $\endgroup$ – Amelio Vazquez-Reina Apr 10 at 12:50
  • 1
    $\begingroup$ Only in the deterministic case. The randomized construction runs in linear time. $\endgroup$ – Yuval Filmus Apr 10 at 12:51
  • $\begingroup$ Fair, although technically my comment above is factually correct ;) $\endgroup$ – Amelio Vazquez-Reina Apr 10 at 12:54
  • 1
    $\begingroup$ I would guess that by now there is a better deterministic construction. $\endgroup$ – Yuval Filmus Apr 10 at 12:55
0
$\begingroup$

Suppose that your hash $h$ function maps $\{1,\ldots,m\}$ to $\{1,\ldots,n\}$, where $m > n$. According to the pigeonhole principle, there exist two inputs $a \neq b$ such that $h(a) = h(b)$. In other words, collisions are unavoidable.

The point of hashing is not that it avoids collisions. Instead, if you choose a random (or random enough) hash function, then collisions are unlikely.

Furthermore, algorithms that use hashing are able to handle collisions. Their performance degrades with the number of collisions. If parameters are chosen so that the average number of collisions is small, then these algorithms will be efficient despite the collisions.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, but in this answer you seem you be discussing "hashing" in general. The CLRS design in my OP is for perfect hashing, and it only involves two levels of hashing. Most importantly, CLRS explicitly states that by choosing $h_j$ we can guarantee that there are no collisions in the 2nd level. In other words, it does claim that this design avoids collisions in the 2nd level. As I mentioned above, the probability of collision in this 2nd level is very low, but still non-zero within each list $0<=j<n$ in the first level. $\endgroup$ – Amelio Vazquez-Reina Apr 10 at 12:15
  • $\begingroup$ Unfortunately I am unable to say anything further, since I don't have access to the book. $\endgroup$ – Yuval Filmus Apr 10 at 12:21
  • $\begingroup$ It might be that the hash function is perfect with overwhelming probability, for example. Or it might be perfect with constant probability, in which case you will have to try a few functions. No way to tell without access to CLRS or an alternative resource. $\endgroup$ – Yuval Filmus Apr 10 at 12:23
  • $\begingroup$ Ok, thanks. This is the reference. I think a low runtime for building the hash table wasn't a major concern for this design since the stated goal is storage of static keys (e.g. long-term archival), but a good runtime could potentially make it useful in more relaxed scenarios. $\endgroup$ – Amelio Vazquez-Reina Apr 10 at 12:29
  • 1
    $\begingroup$ Corollary 4 gives a range of parameters for which the success probability is constant, which means that you have to try $O(1)$ many hash functions on average, and Lemma 2 gives a deterministic construction which is, however, not practical. $\endgroup$ – Yuval Filmus Apr 10 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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