In perfect hashing, why does a secondary hash table that is quadratic in size leads to no collisions?
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.