WorksComputer Science
Exact Failure Probabilities for d-Choice Cuckoo Hashing
Abstract
In d-choice cuckoo hashing, each of n items must be placed in one of its d candidate slots in a table of M slots, and every slot holds at most one item. We give a polynomial-time dynamic programming algorithm to compute the exact probability that no valid placement exists. Our method also handles the variant with separate tables.
Introduction
Cuckoo hashing has been used in a wide range of applications, including key-value stores [6], network switches [20], approximate membership filters [7], page tables [18], and cryptographic protocols [11, 17, 1].
In the basic one-table variant of -choice cuckoo hashing, each of items must be placed in one of its candidate slots in a table of slots, and every slot holds at most one item [15, 10]. We study its failure probability, denoted , that the candidate slots of the items admit no valid placement.
Previous work has established load thresholds for -choice cuckoo hashing [4, 8, 9], and upper bounds on its failure probability [10, 19, 16]. The exact failure probability has also been obtained for [12, 13, 14 DK12], but has remained open for [13 §1.5.3], [1].
Our results. We compute the exact value of for any , , and in time. We use Beniamini’s coefficient formula for perfect matching [2] to express the number of failing outcomes as a sum of exponentially many terms. We then compute this sum using dynamic programming. Our method also extends to the variant with separate tables (possibly of unequal sizes), where it computes in time. The implementations of our algorithms are available at https://github.com/zcy05331/Cuckoo-Failure.
Model and preliminaries
Model
There are items labeled . In the one-table variant, there are slots labeled with $1 \le d < n < M$. Each item independently draws a uniform -element candidate set , and must be placed in one of the slots. Each item thus has possible candidate sets.
An outcome lists the candidate sets of all items, and the outcomes are equally likely. An outcome can be captured by a candidate graph : a bipartite graph with the items on one side, the slots on the other, and an edge for each . A placement of the items is a matching of that covers every item. An outcome leads to a failure if has no such matching. Let be the number of failing outcomes. We have .
We will later consider two variants: independent draws with replacement (§ 3.4) and separate tables (§ 4).
Beniamini's coefficient formula
Beniamini’s expansion. Let be a bipartite graph with left vertices and right vertices, and let denote the complete bipartite graph on the same vertex set. For a left vertex and a right vertex , let if the edge is missing from and otherwise; we call the missing-edge indicators of . Beniamini and Nisan [3] analyze bipartite matching with a multilinear polynomial . is 1 if has no perfect matching and 0 otherwise. They show that this indicator polynomial has integer coefficients as follows [3, 2]:
In the above, ranges over all bipartite graphs on the same vertices. Observe that if every edge of is missing from and 0 otherwise. Beniamini [2] determined the coefficients . To state his formula, we define totally ordered graphs.
Definition 2.1 (Totally ordered graphs [3, 2]). Let be a bipartite graph and be the neighborhood of its -th left vertex. is totally ordered if the neighborhoods of its left vertices are totally ordered by inclusion: for all left vertices and , either or .
For a totally ordered graph , order the distinct neighborhoods of the left vertices as . The left vertices whose neighborhood is form block . Let be their degree, and let be the number of left vertices in blocks , with :

Figure 1. A totally ordered graph with vertices on each side. Rows represent left vertices, columns represent right vertices, and a shaded cell is an edge of . The representing sequence is . It indicates that two left vertices have no neighbors, two left vertices have (the same) three right neighbors, and three left vertices have (the same) five right neighbors.
Block thus consists of left vertices, each of degree . is called the representing sequence of . Figure 1 gives an example. Throughout, we define unless are integers with . Empty products and equal one.
Theorem 2.2 (Beniamini [2 Theorem 2]). If is not totally ordered, then . If is totally ordered with representing sequence (2), then
where
The coefficient in (3) depends on only through its representing sequence. We write it as . Graphs that differ only by permutations of the two vertex sets have the same coefficient.
Dummy items. A candidate graph has item vertices and slot vertices. Since Beniamini’s formula (1) requires an equal number of left vertices and right vertices, we add dummy items that can be placed in any slot. The resulting graph has vertices on each side, and it has a perfect matching if and only if has a matching that covers every left vertex.
Evaluation by dynamic programming
Counting failing outcomes
By (1), the number of failing outcomes is
where ranges over the outcomes and are the missing-edge indicators of .
By Theorem 2.2, only totally ordered graphs can have . If contains an edge incident to a dummy item, that edge is present in for every outcome, so . Thus, only totally ordered graphs in which every dummy item is isolated contribute to (5). Fix such a graph . The monomial equals 1 if and only if every item avoids its neighborhood , that is, . We call the forbidden set of item . If this set has size , the number of candidate sets that avoid it is
The candidate sets of the real items can be chosen independently, so
Substituting into (5) gives
where ranges over the totally ordered graphs in which every dummy item is isolated.
Grouping by representing sequences. Consider a graph that contributes to (8). Let be its representing sequence. Its dummy items are isolated, so they have degree 0 and lie in the first block. Hence and , where is the number of dummy items.
Let and for . Then is the number of real items in block , and . The term associated with in (8) can be rewritten as
because every item of block has a forbidden set of size .
The number of graphs with a given representing sequence can be computed as follows. The real items are distributed among the blocks in ways. The nested sets are chosen in ways. Since , the factor can be omitted. Let be the set of representing sequences with blocks with and . We have
Direct evaluation would have to sum exponentially many nonzero representing sequences. We compute this sum with dynamic programming.
The forward recurrence
Blockwise factorization of each summand. For each representing sequence, we first express its contribution to (9) as a product of blockwise factors. The coefficient already has this form according to (3). Each block contributes , and the last block contributes
The term belongs to block by definition. So does the term. The multinomial coefficient can also be decomposed to individual blocks:
where chooses the items of block among the items not yet placed.
For a nonfinal block , we can think of as the boundary at its start and as the boundary at its end. Let be the number of real items among the first left vertices. The factors associated with a nonfinal block with boundaries and are
For a fixed representing sequence, the corresponding summand in (9) can now be written as
which consists of one multiplier per nonfinal block, and a factor for the final block.
Prefixes with the same boundary can be merged. The factors in (11) depend only on the block’s start and end boundaries, not on earlier blocks. Consider the first blocks of a representing sequence. We define a prefix to consist of these blocks together with . (Note that the end boundary of block is .) The weight of the prefix is
Now extend a prefix by a nonfinal block with start boundary and end boundary . Recall that each representing sequence corresponds to a single summand in (9), which (12) factors into blockwise multipliers. Thus, for any complete representing sequence extending the prefix, its contribution to (9) factors via (12) as
The multiplier is the same for every prefix ending at . We can therefore sum the weights of these prefixes before extending them.
States and recurrence. Define the forward state as the sum of the weights of all prefixes ending at . The empty prefix has the empty forbidden set and is initialized to
All other entries are initially zero. By the binomial convention, in (11) vanishes unless and , so only such entries are assigned below. Extending the prefixes that end at each boundary to gives, for and ,
A final block takes the terminal factor of (12) with all remaining items, so
Each summand of (14) extends the prefixes ending at by one block. By induction on , the recurrence computes as defined, and (15) equals the sum (9).
With states and predecessors per state, the recurrence uses integer operations and cells. Its states depend on ; the next subsection removes this dependence.
Faster evaluation and reuse across table sizes
We further improve the algorithm to by combining three observations.
First, after the initial block of degree 0, the total weight of the remaining blocks depends only on the numbers of remaining real items and available slots , where $0 \le v < p \le n$. We call the remaining blocks a suffix and let denote their total weight. This gives states independent of the table size .
Second, in the recurrence for , the inner sum over the next available-slot count depends only on and the next item count , but not on . Reusing these shared sums splits the transition into two stages and reduces the complexity from to .
Third, the binomial coefficients in both stages can be rearranged into convolution kernels, allowing both the shared sums and the suffix weights to be computed using polynomial multiplication. Using FFT-based polynomial multiplication, the complexity is reduced to .
Independent draws with replacement
Suppose instead that each item makes independent uniform draws from . Its sampling outcome is an ordered -tuple, so . Of these, avoid a forbidden set of size . Apart from these two counts, the algorithms in this section stay unchanged.
Evaluation for separate tables
The model and the state
There are disjoint tables of positive lengths . Each item chooses one slot uniformly from each table, independently across tables and items, and must occupy one of these slots. Write , , and . There are equally likely outcomes; let count those admitting no valid placement. We consider .
The recurrence in § 3.2 tracks the total number of forbidden slots . For separate tables, we need to track the number of forbidden slots in each table. For example, with two tables of length 4, the forbidden counts and both total four but leave and candidate choices per item, respectively. Let denote the number of forbidden slots in each table, and write . An item whose forbidden set has counts has
candidate choices.
For two consecutive blocks, let and denote the counts of their respective forbidden sets in each table. The latter is obtained from the former by choosing additional slots from the remaining slots in each table . The number of possible choices is
This binomial notation will also be used for other quantities.
The forward recurrence
Define the forward state as in § 3.2: the sum of the weights of all prefixes that end at left vertex with a forbidden set of counts .
The multiplier (11) changes in two places: the candidate count becomes , and the set extension becomes . The coefficient factor and the item-choice factor are unchanged:
with , dummy items, and as before. Initialize and all other entries to zero. For and with ,
A final block takes all remaining items, so
and the failure probability is .
Complexity
Apart from , the recurrence (19) produces states with and only. If for some , then : every later item lacks a candidate in table , so every transition from the state and its term in (20) vanish. We therefore keep only states with for every . Put and for the remaining items and the available slots in each table. The retained states satisfy
For each there are at most such vectors , so the recurrence has at most
states. Each state is computed by enumerating all retained predecessors and applying (18). With the binomial coefficients and the powers of precomputed, a transition costs operations. Hence the recurrence uses integer operations and cells for each table-length vector . This is polynomial in for every constant .
Faster evaluation. The suffix formulation of § 3.3 also applies to separate tables. Tracking suffixes by the number of remaining items and the available counts in each table gives a table that depends only on and . Sharing inner sums and applying two binomial transforms builds it in operations, after which each table-length vector is evaluated in operations.
Conclusion
We present dynamic programming algorithms for the exact failure probability of -choice cuckoo hashing for both the one-table and separate-table variants. The algorithms evaluate Beniamini’s expansion by combining prefixes with the same block boundary. For the one-table variant, our algorithm runs in time. For the separate-table variant, our algorithm runs in time for constant . A direction for future work is to find an algorithm for separate tables that is polynomial in both and .
References
- [1][ACLS18] Sebastian Angel, Hao Chen, Kim Laine, and Srinath Setty. PIR with compressed queries and amortized query processing. In 2018 IEEE Symposium on Security and Privacy (SP), pages 962–979. IEEE, 2018.DOI
- [2][Ben22] Gal Beniamini. The approximate degree of bipartite perfect matching. In Proceedings of the 37th Computational Complexity Conference, CCC ’22, Dagstuhl, DEU, 2022. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
- [3][BN21] Gal Beniamini and Noam Nisan. Bipartite perfect matching as a real polynomial. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1118–1131, 2021.
- [4]Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, and Michael Rink. Tight thresholds for cuckoo hashing via xorsat. In International Colloquium on Automata, Languages, and Programming, pages 213–225. Springer, 2010.arxiv.org/abs/0912.0287
- [6]Bin Fan, David G. Andersen, and Michael Kaminsky. MemC3: Compact and concurrent Mem-Cache with dumber caching and smarter hashing. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13), pages 371–384. USENIX Association, 2013.
- [7]Bin Fan, David G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. Cuckoo filter: Practically better than Bloom. In Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies, pages 75–88. ACM, 2014.
- [8]Alan Frieze and Páll Melsted. Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables. Random Structures & Algorithms, 41(3):334–364, 2012.DOI
- [9]Nikolaos Fountoulakis and Konstantinos Panagiotou. Sharp load thresholds for cuckoo hashing. Random Structures & Algorithms, 41(3):306–333, 2012.arxiv.org/abs/0910.5147
- [10]Dimitris Fotakis, Rasmus Pagh, Peter Sanders, and Paul Spirakis. Space efficient hash tables with worst case constant access time. Theory of Computing Systems, 38(2):229–248, 2005.
- [11]Michael T. Goodrich and Michael Mitzenmacher. Privacy-preserving access of outsourced data via oblivious RAM simulation. In International Colloquium on Automata, Languages, and Programming, pages 576–587. Springer, 2011.arxiv.org/abs/1007.1259
- [12]Reinhard Kutzelnigg. Bipartite random graphs and cuckoo hashing. In Fourth Colloquium on Mathematics and Computer Science, volume AG of DMTCS Proceedings, pages 403–406, 2006.DOI
- [13]Reinhard Kutzelnigg. Random Bipartite Graphs and their Application to Cuckoo Hashing. PhD thesis, Technische Universität Wien, 2008.
- [14]Reinhard Kutzelnigg. A further analysis of cuckoo hashing with a stash and random graphs of excess r. Discrete Mathematics & Theoretical Computer Science, 12(3):81–102, 2010.DOI
- [15]Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. Journal of Algorithms, 51(2):122–144, 2004.
- [16]Ely Porat and Bar Shalem. A cuckoo hashing variant with improved memory utilization and insertion time. In 2012 Data Compression Conference, pages 347–356. IEEE, 2012.arxiv.org/abs/1104.5400
- [17]Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. Phasing: Private set intersection using permutation-based hashing. In 24th USENIX Security Symposium, pages 515–530. USENIX Association, 2015.
- [18]Dimitrios Skarlatos, Apostolos Kokolis, Tianyin Xu, and Josep Torrellas. Elastic cuckoo page tables: Rethinking virtual memory translation for parallelism. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1093–1108, 2020.
- [19]Kevin Yeo. Cuckoo hashing in cryptography: Optimal parameters, robustness and applications. In Advances in Cryptology – CRYPTO 2023, pages 197–230. Springer Nature Switzerland, 2023.arxiv.org/abs/2306.11220
- [20]Dong Zhou, Bin Fan, Hyeontaek Lim, Michael Kaminsky, and David G. Andersen. Scalable, high performance ethernet forwarding with cuckooswitch. In Proceedings of the ninth ACM conference on Emerging networking experiments and technologies, pages 97–108, 2013.DOI