An analysis of random-walk cuckoo hashing

DOI10.1137/090770928MaRDI QIDQ5892635zbMATH OpenOpenAlexWikidataFDO

Authors Páll Melsted, Michael Mitzenmacher, Alan Frieze

Publication date 29 July 2011

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/090770928

zbMATH Keywords

cuckoohashingrandom walk

Mathematics Subject Classification ID

Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• An Analysis of Random-Walk Cuckoo Hashing
• On the insertion time of cuckoo hashing
• On the insertion time of random walk cuckoo hashing
• On the insertion time of random walk cuckoo hashing
• Cuckoo hashing: Further analysis

Cited in

(17)

• Balanced allocation through random walk
• Dynamic space efficient hashing
• A faster algorithm for cuckoo insertion and bipartite matching in large graphs
• Hardness-preserving reductions via cuckoo hashing
• scientific article; zbMATH DE number 5989968 (Why is no real title available?)
• Sharp load thresholds for cuckoo hashing
• Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes
• On the insertion time of random walk cuckoo hashing
• Greedy matching in bipartite random graphs
• Dynamic space efficient hashing
• Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions
• On the insertion time of random walk cuckoo hashing
• On the insertion time of cuckoo hashing
• On probabilistic analysis of a coalesced hashing algorithm
• An Analysis of Random-Walk Cuckoo Hashing
• An improved version of cuckoo hashing: average case analysis of construction cost and search operations
• Insertion time of random walk cuckoo hashing below the peeling threshold

This page was built for publication: An analysis of random-walk cuckoo hashing

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