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

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?

• Using two hash tables of size $n$, as you specify, means we can actually insert slightly less than $n$ keys, not $n/2$. – jbapple Jun 23 '19 at 3:33

## 1 Answer

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}

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.