On the insertion time of random walk cuckoo hashing

DOI10.1002/RSA.20808MaRDI QIDQ5229339zbMATH OpenOpenAlexFDO

Authors Tony Johansson, Alan Frieze

Publication date 14 August 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.04652

zbMATH Keywords

cuckoo hashinginsertion timerandom walk

Mathematics Subject Classification ID

Random walks on graphs (05C81) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Cuckoo Hashing is a hashing scheme invented by Pagh and Rodler. It uses $dgeq2$ distinct hash functions to insert items into the hash table. It has been an open question for some time as to the expected time for Random Walk Insertion to add items. We show that if the number of hash functions $d=O(1)$ is sufficiently large, then the expected insertion time is $O(1)$ per item.

Recommendations

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

Cited in

(7)

• scientific article; zbMATH DE number 5989968 (Why is no real title available?)
• On the insertion time of random walk cuckoo hashing
• On the insertion time of cuckoo hashing
• An analysis of random-walk cuckoo hashing
• 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: On the insertion time of random walk cuckoo hashing

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