Building a perfect hashing table

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.