An improved version of cuckoo hashing: average case analysis of construction cost and search operations

DOI10.1007/s11786-009-0005-xzbMath1205.68532OpenAlexW1981786992MaRDI QIDQ626960

Reinhard Kutzelnigg

Publication date: 19 February 2011

Published in: Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11786-009-0005-x

zbMATH Keywords

algorithmshashingcuckoo hashingopen addressing

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Asymptotic enumeration (05A16)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cuckoo hashing: Further analysis
• Universal classes of hash functions
• Linear probing and graphs
• A bivariate asymptotic expansion of coefficients of powers of generating functions
• Perfect hashing
• Space efficient hash tables with worst case constant access time
• On the number of bases of bicircular matroids
• Some results on the asymptotic behaviour of coefficients of large powers of functions
• Balanced allocation and dictionaries with tightly packed constant size bins
• A precise analysis of Cuckoo hashing
• Saddle-point Methods for the Multinomial Distribution
• How asymmetry helps load balancing
• Almost random graphs with simple hash functions
• Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Balanced Allocations
• Cuckoo hashing
• The birth of the giant component
• Two-Way Chaining with Reassignment
• Reducing the retrieval time of scatter storage techniques
• More Robust Hashing: Cuckoo Hashing with a Stash

This page was built for publication: An improved version of cuckoo hashing: average case analysis of construction cost and search operations