Iceberg hashing: optimizing many hash-table criteria at once

DOI10.1145/3625817MaRDI QIDQ7031999zbMATH OpenFDO

Authors Michael A. Bender, Alex Conway, Martin Farach-Colton, William Kuszmaul, Guido Tagliavini

Publication date 5 February 2025

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3625817

zbMATH Keywords

dynamic resizinghashingstability

Mathematics Subject Classification ID

Data structures (68P05)

Cites work

• A hash table without hash functions, and how to get the most out of your random bits
• Almost random graphs with simple hash functions
• Analysis of Uniform Hashing
• Backyard cuckoo hashing: constant worst-case operations with a succinct representation
• Balanced allocation and dictionaries with tightly packed constant size bins
• Bloom filters, adaptivity, and the dictionary problem
• Cache-oblivious dictionaries and multimaps with negligible failure probability
• Cache-oblivious hashing
• Cuckoo hashing
• De Dictionariis Dynamicis Pauco Spatio Utentibus
• De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Deterministic dictionaries
• Dynamic integer sets with optimal rank, select, and predecessor search
• Dynamic space efficient hashing
• How to Construct Pseudorandom Permutations from Pseudorandom Functions
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3664386 (Why is no real title available?)
• scientific article; zbMATH DE number 177800 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1962820 (Why is no real title available?)
• scientific article; zbMATH DE number 2038723 (Why is no real title available?)
• scientific article; zbMATH DE number 1445338 (Why is no real title available?)
• scientific article; zbMATH DE number 7759279 (Why is no real title available?)
• Linear probing revisited: tombstones mark the demise of primary clustering
• On the construction of pseudorandom permutations: Luby-Rackoff revisited
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Optimal hashing in external memory
• Optimality in external memory hashing
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• The limits of buffering: a tight lower bound for dynamic membership in the external memory model
• The power of simple tabulation hashing
• Tiny pointers
• Uniform deterministic dictionaries
• Uniform Hashing in Constant Time and Optimal Space
• Using hashing to solve the dictionary problem

Cited in

(6)

• Dynamic filter and retrieval with one access to modifiable memory
• Paging and the address-translation problem
• Tiny pointers
• Approximate suffix-prefix dictionary queries
• Sparse suffix and LCP array: simple, direct, small, and fast
• Shortest undirected paths in de Bruijn graphs

This page was built for publication: Iceberg hashing: optimizing many hash-table criteria at once

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