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.

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

... collisions are still possible in this second level

For each slot of the first-level hash table (which contains more than 1 keys), we will need to decide a hash-function. Since we want perfect-hashing, we want this function to give no collision. Theorem 11.9 (quoted below) guides us that it is in-fact possible to find such a function in a universal-class, with probability atleast 1/2 (meaning, atleast half of them are collision-free for this slot's keys). So, with a very few random trials, we can hope to succeed in finding such function. With each trial, we need to check all keys in that slot to know if this is the one which works. And this task needs to be repeated for all slots of first-level table.

So, collisions are possible if we simply pick this second-level hash function randomly, without checking/ensuring as above. A collision-free function can be found with a one-time exercise (since keys are static) as above.

... 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.

True, for each value of j. Each slot contains different set of keys, and so the non-collision function needs to be worked out separately for each slot's set of keys.

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?

Since our aim is no collisions at the second-level, I think the individual sets of keys in each slot does require the trial-error, because the hash functions outcome really depends upon the input keys. (I have not yet checked the Fredman's (et al.) paper you referenced).

Theorem 11.9, quoted (CLRS): "If we store $n$ keys in a hash table of size $m=n^2$ using a hash function $h$ randomly chosen from a universal class of hash functions, then the probability of there being any collisions is less than 1/2."

$\endgroup$
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.

$\endgroup$
8
  • $\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 '20 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 '20 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 '20 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 '20 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 '20 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.