# 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?