New answers tagged

3

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 $\...


Top 50 recent answers are included