Load Thresholds for Cuckoo Hashing with Double Hashing

Michael Mitzenmacher, Konstantinos Panagiotou, Stefan Walzer

TL;DR

This paper proves that a simplified hashing technique called "double hashing" achieves the same theoretical performance limits (load thresholds) as standard, fully random hashing in the context of cuckoo hashing. This is significant because double hashing is simpler and more efficient in practice, and this work finally bridges a gap in understanding why it performs just as well theoretically.

What Problem Does This Paper Address?

Cuckoo hashing is a popular data structure for storing items in a hash table. In its "k-ary" version, each item is assigned to $k$ potential "buckets" (locations in the hash table). The goal is to find an assignment where no bucket gets overloaded, specifically, each bucket receives at most $l$ items. Researchers have determined a "load threshold," $c^*$, which is the maximum load (ratio of items to buckets) for which such an assignment is likely to exist.

A practical simplification is "double hashing," where the $k$ bucket choices for an item are not entirely random but follow an arithmetic progression. This reduces the need for truly random hash functions. While double hashing has been shown to perform similarly to random hashing in many other contexts, there was a lingering theoretical question: does it achieve the exact same load threshold in cuckoo hashing? Previous work showed they were almost the same, but a small fraction of items ($o(n)$) could still be left unplaced with double hashing, unlike with fully random hashing. This paper aims to close that gap and prove the thresholds are identical.

Methods

The core of the paper's contribution lies in a novel combinatorial argument to bridge the theoretical gap between double hashing and fully random hashing for cuckoo hashing.

  • Hypergraph Orientability: The problem is framed in terms of hypergraph orientability. A hypergraph represents items as vertices and buckets as edges. An "l-orientation" is an assignment of edges to vertices such that each vertex is assigned at most $l$ edges. The load threshold $c^*$ corresponds to the point where such an l-orientation becomes impossible with high probability.
  • Hall's Theorem Generalization: The paper leverages a generalization of Hall's Marriage Theorem. This theorem states that an l-orientation exists if and only if no "Hall-witness" exists. A Hall-witness is a subset of items that collectively "demand" more bucket capacity than is available to them.
  • Combinatorial Argument: The key innovation is a combinatorial argument to show that for double hashing, the probability of having "small" Hall-witnesses (those with fewer than $\delta n$ items) is negligible. This is achieved by carefully analyzing the structure of arithmetic progressions in the double hashing scheme and using probabilistic bounds. The proof proceeds by showing that if a hypergraph is not l-orientable, and we remove an edge from a minimal Hall-witness, the resulting structure is still "almost" l-orientable, allowing for a step-by-step reduction of the "unplaced items" count until it reaches zero.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Double Hashing is Truly Equivalent: The paper definitively proves that double hashing, despite its simpler mechanism, achieves the exact same theoretical load threshold as fully random hashing for k-ary cuckoo hashing. This is a strong theoretical validation for using double hashing in practice.
  • Combinatorial Arguments are Powerful: The success in closing the theoretical gap relied on a sophisticated combinatorial argument, demonstrating the power of this approach for analyzing hashing schemes.
  • Hall's Theorem as a Unifying Tool: The paper highlights how Hall's Theorem and the concept of Hall-witnesses provide a robust framework for understanding and proving properties of hashing structures.
  • The "Stubborn Difference" is Resolved: The paper directly addresses and resolves a specific, persistent theoretical anomaly that had previously prevented full equivalence between random and double hashing for cuckoo hashing.

Key Results

The main result is Theorem 1, which states that for fixed $k \ge 3$ and $l \ge 1$, the l-orientability threshold for $k$-ary cuckoo hashing using fully random bucket selection is identical to the threshold when using double hashing. This means that for loads below this threshold, an l-orientation exists with high probability in both scenarios, and for loads above, it does not.

Limitations and Future Work

  • Generalization to $o(n)$-cores: The authors note that their current approach, while successful for l-orientability, cannot yet rule out small $o(n)$-sized "l-cores" in double hashing scenarios. An l-core is what remains after repeatedly removing vertices with degree less than $l$. This is a related problem in random hypergraphs, and settling it for double hashing remains an open question.
  • Unified Argument: The authors express a desire for a more unified theoretical argument that could explain the equivalence of double hashing and random hashing across various data structures, rather than requiring specialized proofs for each.
  • Practical Implications: While the theoretical result is strong, further work could explore the practical performance implications of this equivalence in real-world cuckoo hashing implementations.

Summary updated

Abstract

In k-ary cuckoo hashing, each of cn objects is associated with k random buckets in a hash table of size n. An l-orientation is an assignment of objects to associated buckets such that each bucket receives at most l objects. Several works have determined load thresholds c^* = c^*(k,l) for k-ary cuckoo hashing; that is, for c < c^* an l-orientation exists with high probability, and for c > c^* no l-orientation exists with high probability. A natural variant of k-ary cuckoo hashing utilizes double hashing, where, when the buckets are numbered 0,1,...,n-1, the k choices of random buckets form an arithmetic progression modulo n. Double hashing simplifies implementation and requires less randomness, and it has been shown that double hashing has the same behavior as fully random hashing in several other data structures that similarly use multiple hashes for each object. Interestingly, previous work has come close to but has not fully shown that the load threshold for k-ary cuckoo hashing is the same when using double hashing as when using fully random hashing. Specifically, previous work has shown that the thresholds for both settings coincide, except that for double hashing it was possible that o(n) objects would have been left unplaced. Here we close this open question by showing the thresholds are indeed the same, by providing a combinatorial argument that reconciles this stubborn difference.
BibTeX
@inproceedings{mitzenmacher2018load,
  author = {Michael Mitzenmacher and Konstantinos Panagiotou and Stefan Walzer},
  title = {{Load Thresholds for Cuckoo Hashing with Double Hashing}},
  booktitle = {SWAT},
  year = {2018},
  doi = {10.4230/lipics.swat.2018.29},
}

Loading related content...

Figure