What is the maximal load of a “latency-bounded” Cuckoo Hash?

Question

Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time.

They use two hash functions $h_1,h_2:\mathbb K\to [n]$, where $\mathbb K$ is the set of keys, and $[n]=\{1,\ldots,n\}$ are indices of the array in which we store the data.

Whenever we wish to insert a key $k$, we first check if there is either $h_1(k)$ or $h_2(k)$ are free. Otherwise, we insert it into $h_2(k)$ by replacing the key $k'$ that was stored there. If $h_1(k')$ is free then we're done, otherwise, we replace the key that is there $k''$ which then looks for $h_2(k'')$ and so forth.

This operation may fail if there is a loop of keys trying to evict each other.

It is known that if the load of the hash table is at most half (i.e., we don't insert more than $n/2$ keys), with high probability all operations succeed.

I'm interested in the load I can use without making more than $T$ evictions for some $T\in\mathbb N$.

Clearly, smaller $T$ will allow smaller load. For example, if $T=0$ (no eviction permitted), then we cannot load more than $O(\sqrt n)$ elements without getting a colision.

How many elements can we insert for larger $T$ so that we succeed, say, with probability 9/10?

Answer 1

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 $\epsilon \approx 0.221$. The first term is basically negligible.