In perfect hashing, why does a secondary hash table that is quadratic in size leads to no collisions? See below a screenshot from CLRS 3rd Edition (Section 11.5, "Perfect Hashing"). The last sentence of the last paragraph says that the choice of $m_j = n^2_j$ leads to collision-free constant-time lookup. 

Why? Is it because:


It assumes that one could, in theory, try or sample several hashing functions $\mathcal{h} \in \mathcal{H}$, checking for each for collisions, until we find one $h'$ that doesn't have them?
the probability of sampling $h$ without collisions is 1/2, so it shouldn't be that difficult to find $h'$?


If not, why?
If $n_j$ keys hash to slot $j$ of the first-level hashtable, and if $n_j &gt; 1$, we will need to use a second-level hashtable for that slot. Theorem 11.9 helps us in the sense that, if we keep this second hashtable size as $n_j^2$, then atleast 1/2 of the hash-functions in any universal-class (which all hash to range 0 to $n_j^2-1$) must give no collisions for the $n_j$ keys.
We can NOT conclude that if we pick any random function from this class, we will have a collision-free case. We will need to do some trials, and can hope to succeed for this set of $n_j$ keys very soon, due to the 1/2 probability provided by Theorem 11.9.
Please also refer below answer for details:
https://cs.stackexchange.com/a/134386/123596.