<p>Section 4 of <a href="https://www.cs.tau.ac.il/~shanir/advanced-seminar-data-structures-2009/bib/pagh01cuckoo.pdf" rel="nofollow noreferrer">the journal version of the original Cuckoo Hashing paper</a> shows that to have insertion succeed with probability <span class="math-container">$p$</span>, your numbers <span class="math-container">$T$</span>, <span class="math-container">$n$</span>, and <span class="math-container">$\epsilon$</span> must satisfy</p>

<p><span class="math-container">$$
\frac{13}{n^2 \epsilon}
+
2(1+\epsilon)^
{1-(2T-1)/3}
&lt;p
$$</span></p>

<p>where the two sub-tables are of size <span class="math-container">$n(1+\epsilon)$</span>.</p>

<p>So for <span class="math-container">$p = 9/10$</span>, <span class="math-container">$T=8$</span>, and <span class="math-container">$n=1,000,000$</span>, we get <span class="math-container">$\epsilon \approx 0.221$</span>. The first term is basically negligible.</p>

CC BY-SA 4.0
2019-06-23T04:15:02.623Z
2019-06-23T04:15:02.623Z
jbapple
<p>Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time.</p>

<p>They use two hash functions <span class="math-container">$h_1,h_2:\mathbb K\to [n]$</span>, where <span class="math-container">$\mathbb K$</span> is the set of keys, and <span class="math-container">$[n]=\{1,\ldots,n\}$</span> are indices of the array in which we store the data.</p>

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

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

<p>It is known that if the load of the hash table is at most half (i.e., we don't insert more than <span class="math-container">$n/2$</span> keys), with high probability all operations succeed.</p>

<p>I'm interested in the load I can use without making more than <span class="math-container">$T$</span> evictions for some <span class="math-container">$T\in\mathbb N$</span>.</p>

<p>Clearly, smaller <span class="math-container">$T$</span> will allow smaller load. For example, if <span class="math-container">$T=0$</span> (no eviction permitted), then we cannot load more than <span class="math-container">$O(\sqrt n)$</span> elements without getting a colision.</p>

<blockquote>
  <p>How many elements can we insert for larger <span class="math-container">$T$</span> so that we succeed, say, with probability 9/10?</p>
</blockquote>

CC BY-SA 4.0
2019-06-23T03:33:53.097Z
Using two hash tables of size $n$, as you specify, means we can actually insert slightly less than $n$ keys, not $n/2$.
jbapple
<ds.algorithms><randomized-algorithms><hash-function>
What is the maximal load of a "latency-bounded" Cuckoo Hash?
R B
# What is the maximal load of a "latency-bounded" Cuckoo Hash?

(Asked by: username_0 on 2018-10-19)

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?

**Tags:** ds.algorithms, randomized-algorithms, hash-function
> **Comments:**
> **username_1**: Using two hash tables of size $n$, as you specify, means we can actually insert slightly less than $n$ keys, not $n/2$.  

---

## 1 answers

### Answer by username_1 on 2019-06-23. Score: 3 | Accepted answer

Section 4 of [the journal version of the original Cuckoo Hashing paper](https://www.cs.tau.ac.il/~shanir/advanced-seminar-data-structures-2009/bib/pagh01cuckoo.pdf) 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.


---

