1.56 bits per key is now possible using "RecSplit: Minimal Perfect Hashing via Recursive Splitting" by Emmanuel Esposito, Thomas Mueller Graf, and Sebastiano Vigna. It is quite expensive: 1,700 times more expensive than 1.79 bits per key!


Section 4 of the journal version of the original Cuckoo Hashing paper shows that to have insertion succeed with probability $p$, your numbers $T$, $n$, and $\epsilon$ must satisfy $$ \frac{13}{n^2 \epsilon} + 2(1+\epsilon)^ {1-(2T-1)/3} <p $$ where the two sub-tables are of size $n(1+\epsilon)$. So for $p = 9/10$, $T=8$, and $n=1,000,000$, we get $\...

Only top voted, non community-wiki answers of a minimum length are eligible