On the insertion time of cuckoo hashing

DOI10.1137/100797503MaRDI QIDQ5408762zbMATH OpenOpenAlexFDO

Authors Nikolaos Fountoulakis, Angelika Steger, Konstantinos Panagiotou

Publication date 11 April 2014

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

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

zbMATH Keywords

hashinginformation retrievalrandom graphs and hypergraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Abstract data types; algebraic specification (68Q65)

Abstract: Cuckoo hashing is an efficient technique for creating large hash tables with high space utilization and guaranteed constant access times. There, each item can be placed in a location given by any one out of k different hash functions. In this paper we investigate further the random walk heuristic for inserting in an online fashion new items into the hash table. Provided that k > 2 and that the number of items in the table is below (but arbitrarily close) to the theoretically achievable load threshold, we show a polylogarithmic bound for the maximum insertion time that holds with high probability.

Recommendations

• An Analysis of Random-Walk Cuckoo Hashing
• An analysis of random-walk 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

(22)

• Cuckoo hashing: Further analysis
• Balanced allocation through random walk
• Dynamic space efficient hashing
• A faster algorithm for cuckoo insertion and bipartite matching in large graphs
• Random-index PIR and applications
• scientific article; zbMATH DE number 5989968 (Why is no real title available?)
• Sharp load thresholds for cuckoo hashing
• Wear minimization for cuckoo hashing: how not to throw a lot of eggs into one basket
• Some Open Questions Related to Cuckoo Hashing
• 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit
• scientific article; zbMATH DE number 1962820 (Why is no real title available?)
• On the insertion time of random walk cuckoo hashing
• Dynamic space efficient hashing
• On the insertion time of random walk cuckoo hashing
• Two-Way Chaining with Reassignment
• An analysis of random-walk cuckoo hashing
• An Analysis of Random-Walk Cuckoo Hashing
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• Cuckoo hashing in cryptography: optimal parameters, robustness and applications
• An improved version of cuckoo hashing: average case analysis of construction cost and search operations
• Cuckoo commitments: registration-based encryption and key-value map commitments for large spaces
• Insertion time of random walk cuckoo hashing below the peeling threshold

This page was built for publication: On the insertion time of cuckoo hashing

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