A further analysis of Cuckoo Hashing with a Stash and Random Graphs of Excess r

Cuckoo hashing is a hash table data structure offering constant access time, even in the worst case. As a drawback, the construction fails with small, but practically significant probability. However, Kirsch et al. (2008) showed that a constant-sized additional memory, the so called stash, is sufficient to reduce the failure rate drastically. But so far, using a modified insertion procedure that demands additional running time to look for an admissible key is required. As a major contribution of this paper, we show that the same bounds on the failure probability hold even without this search process and thus, the performance increases. Second, we extend the analysis to simplified cuckoo hashing, a variant of the original algorithm offering increased performance. Further, we derive some explicit asymptotic approximations concerning the number of usual resp. bipartite graphs related to the data structures. Using these results, we obtain much more precise asymptotic expansions of the success rate. These calculations are based on a generating function approach and applying the saddle point method. Finally, we provide numerical results to support the theoretical analysis.

• Publication year

  2010

• Venue

  Discrete Mathematics & Theoretical Computer Science

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.46298/dmtcs.495
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A precise analysis of Cuckoo hashing

  2012cited by this paper
• An Improved Version of Cuckoo Hashing: Average Case Analysis of Construction Cost and Search Operations

  2010influential reference
• Analytic Combinatorics

  2009influential reference
• On risks of using cuckoo hashing with simple universal hash classes

  2009cited by this paper
• More Robust Hashing: Cuckoo Hashing with a Stash

  2008influential reference
• On the Number of Bases of Bicircular Matroids

  2005cited by this paper
• Balanced allocation and dictionaries with tightly packed constant size bins

  2005cited by this paper
• Space Efficient Hash Tables with Worst Case Constant Access Time

  2003cited by this paper
• Cuckoo hashing: Further analysis

  2003influential reference
• Cuckoo Hashing

  2001influential reference
• The Art of Computer Programming: Volume 3: Sorting and Searching

  1998cited by this paper
• Introduction to algorithms

  1996cited by this paper
• Some results on the asymptotic behaviour of coefficients of large powers of functions

  1995cited by this paper
• A Bivariate Asymptotic Expansion of Coefficients of Powers of Generating Functions

  1994influential reference
• The Birth of the Giant Component

  1993influential reference
• The Art of Computer Programming

  1968cited by this paper
• Saddle-point Methods for the Multinomial Distribution

  1957cited by this paper

• A novel multithresholding algorithm for segmentation of the MRI images

  2023cites this paper
• Un nuevo algoritmo multiumbral para la segmentación de imágenes de resonancia magnética

  2023cites this paper
• Explicit, Closed-form, General bounds for Cuckoo Hashing with a Stash

  2022cites this paper
• A survey on Cuckoo Search Algorithm for Optimization Problems

  2021cites this paper
• Hashing , Load Balancing and Multiple Choice DRAFT ∗

  2017cites this paper
• Hashing, Load Balancing and Multiple Choice

  2017cites this paper
• Maximizing the Throughput of Hash Tables in Network Devices with Combined SRAM/DRAM Memory

  2015cites this paper
• Thresholds for Matchings in Random Bipartite Graphs with Applications to Hashing-Based Data Structures

  2015cites this paper
• Enhanced chained and Cuckoo hashing methods for multi-core CPUs

  2014cites this paper
• Fast decisions in high-Speed networking devices

  2014cites this paper
• Performance Analysis of Hashing Techniques for Multi-core CPUs

  2013cites this paper
• The Structure of an Evolving Random Bipartite Graph

  2012cites this paper
• Statistical and Machine Learning Approaches for Network Analysis

  2012cites this paper
• Maximizing the Throughput of Cuckoo Hashing in Network Devices

  2012cites this paper
• Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash

  2012influential citation
• Hash tables with finite buckets are less resistant to deletions

  2010cites this paper
• Maximum Bipartite Matching Size And Application to Cuckoo Hashing

  2010cites this paper