3
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.