## 4 Theoretical Analysis
### Search Failure Probability
#### 4.2.2. Cuckoo Hash Table  
A false negative that results in search failure in a cuckoo hash table also occurs when searching an element that could not be inserted. Figure 2 shows a case where an element cannot be stored in a cuckoo hash table. In inserting 3 elements, \(x_{1}\), \(x_{2}\), and \(x_{3}\), in sequence, if \(h_{1}(x_{1})=h_{1}(x_{2})=h_{1}(x_{3})\) and \(h_{2}(x_{1})=h_{2}(x_{2})=h_{2}(x_{3})\), element \(x_{3}\) cannot be stored, as two loops occur. The insertion procedure should stop; otherwise, the insertion procedure will repeat infinitely.  
To find the upper bound of probability that an element cannot be stored in a cuckoo hash table because of two loops, assume that the \(2(i-1)\) indexes of \(i-1\) elements are mapped to only \(i-1\) buckets and elements are evenly distributed to both tables (the difference between the number of occupied buckets in the first table and the second table is equal to 0 or 1). When the \(i^{th}\) element needs to be inserted, if the \(i^{th}\) element selects two (one in each table) of the \(i-1\) buckets, two loops occur. Let \(P_{c}\) represent the probability that an element cannot be stored in a cuckoo hash table because of two loops. Assuming that \(n\) is even, then \(P_{c}\) is formulated as follows.  
\[P_{c} \leq\frac{1}{n}\Big{(}0^{2}+0^{2}+(\frac{1}{B_{c}}\cdot\frac{1}{B _{c}})+(\frac{2}{B_{c}}\cdot\frac{1}{B_{c}})+\cdots+(\frac{\frac{n-2}{2B_{c}}} {\cdot\frac{n-2}{B_{c}}})+(\frac{\frac{n}{2}}{B_{c}}\cdot\frac{\frac{n-2}{2}} {B_{c}})\Big{)}\] \[=\frac{1}{nB_{c}}^{2}\Big{(}\sum_{j=1}^{\frac{n-2}{2}}j^{2}+\sum_ {j=1}^{\frac{n}{2}}j(j-1)\Big{)} \tag{19}\]  
As \(P_{c}\) has to be handled depending on whether the \(i^{th}\) element is an odd-numbered or an even-numbered element, the summation in Label (19) consists of two types of sequences for \(j\). Because \(B_{c}=B_{m}\), and assuming that \(n\) is very large, Label (19) can be formulated as follows.  
Figure 2: Element \(x_{3}\) cannot be stored because of two loops in a cuckoo hash table.  
\[P_{c} \leq \frac{1}{nB_{c}{2}}\Big{(}\sum_{j=1}^{\frac{n-2}{2}}j^{2}+\sum_{j=1} ^{\frac{n}{2}}j(j-1)\Big{)}=\frac{1}{24B_{c}{2}}(2n^{2}-3n-2) \tag{20}\] \[= \frac{\alpha^{2}(2n^{2}-3n-2)}{6n^{2}}\approx\frac{\alpha^{2}}{3}\]  
where \(\alpha\) is the load factor of a multi-hash table. When \(n\) is odd, the same result is also obtained.  
Let \(P(F_{c})\) represent the _false negative_ probability of a cuckoo hash table. For \(3n\) inputs, as \(P(F_{c}|S^{c})=0\), the \(P(F_{c})\) has the following upper bound.  
\[P(F_{c}) = P(S)P(F_{c}|S)+P(S^{c})P(F_{c}|S^{c}) \tag{21}\] \[= P(S)P(F_{c}|S)=\frac{1}{3}P_{c}\leq\frac{\alpha^{2}}{9}\]  
Labels (20) and (21) hold true when \(\alpha\leq 1\). In case of \(\alpha>1\), the number of elements is more than the number of entries in a hash table (i.e., \(n>2B_{c}\)). Assuming that no empty entry exists in a hash table when the number of programmed elements is \(2B_{c}\), the \(i^{th}\) element cannot be inserted in the table for \(2B_{c}<i\leq n\). In other words, in calculating \(P_{c}\) for \(\alpha>1\), the probability that the \(i^{th}\) element cannot be inserted is 1, which means collision unavoidably occurs. Thus, for \(\alpha>1\), \(P_{c}\) is derived as follows.  
\[P_{c} \leq \frac{1}{n}\Big{(}0^{2}+0^{2}+(\frac{1}{B_{c}}\cdot\frac{1}{B_{c}} )+(\frac{2}{B_{c}}\cdot\frac{1}{B_{c}})+\cdots+(\frac{\frac{2B_{c}-2}{2}}{B_{ c}}\cdot\frac{\frac{2B_{c}-2}{2}}{B_{c}})+(\frac{2\frac{2B_{c}}{2}}{B_{c}}\cdot \frac{\frac{2B_{c}-2}{2}}{B_{c}})+(n-2B_{c})\Big{)} \tag{22}\] \[= \frac{1}{n}\Big{(}\frac{1}{B_{c}{2}}\big{(}\sum_{j=1}^{B_{c}-1}j ^{2}+\sum_{j=1}^{B_{c}}j(j-1)\big{)}+(n-2B_{c})\Big{)}\] \[\approx 1-\frac{2}{3\alpha}\]  
Therefore, \(P(F_{c})\) for \(\alpha>1\) has the following upper bound.  
\[P(F_{c})=P(S)P(F_{c}|S)=\frac{1}{3}P_{c}\leq\frac{1}{3}\Big{(}1-\frac{2}{3 \alpha}\Big{)} \tag{23}\]