Cuckoo hashing: Further analysis

DOI10.1016/S0020-0190(02)00500-8zbMath1162.68832MaRDI QIDQ1007604

Pat Morin, Luc P. Devroye

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

algorithms; probabilistic analysis of algorithms; hashing; cuckoo hashing; open addressing; collision resolution; worst-case search time

Mathematics Subject Classification ID

68W40: Analysis of algorithms

Related Items

An improved version of cuckoo hashing: average case analysis of construction cost and search operations, Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes

Cites Work

• Balanced allocations (extended abstract)
• The expected length of the longest probe sequence for bucket searching when the distribution is not uniform
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Membership in Constant Time and Almost-Minimum Space
• Balanced Allocations
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Studying Balanced Allocations with Differential Equations
• Polynomial hash functions are reliable
• Probability Inequalities for Sums of Bounded Random Variables
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item