Building a perfect hashing table 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 &lt; 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?
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.