Cuckoo hashing: Further analysis

DOI10.1016/S0020-0190(02)00500-8zbMATH Open1162.68832MaRDI QIDQ1007604FDOQ1007604

Pat Morin, Luc Devroye

Publication date: 23 March 2009

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

zbMATH Keywords

algorithmsprobabilistic analysis of algorithmshashingcuckoo hashingopen addressingcollision resolutionworst-case search time

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Cites Work

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

Cited In (12)

• Layered hashing algorithm for real-time systems
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• Dynamic space efficient hashing
• Cuckoo hashing in cryptography: optimal parameters, robustness and applications
• Explicit and efficient hash families suffice for cuckoo hashing with a stash
• Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes
• Pseudo-random graphs and bit probe schemes with one-sided error
• Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables
• Sharp load thresholds for cuckoo hashing
• Title not available (Why is that?)
• An improved version of cuckoo hashing: average case analysis of construction cost and search operations
• Dynamic Space Efficient Hashing.

This page was built for publication: Cuckoo hashing: Further analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1007604)