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?