Uniform Hashing in Constant Time and Optimal Space

DOI10.1137/060658400MaRDI QIDQ3614151zbMATH OpenOpenAlexFDO

Authors Anna Pagh, Rasmus Pagh

Publication date 16 March 2009

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

Full work available at URL https://semanticscholar.org/paper/3c3ef36f91bcd4b8b7abbb4212169c78751ef87b

zbMATH Keywords

hash functionrandomized algorithmsuniform hashing

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Recommendations

• Uniform hashing in constant time and linear space
• The computational complexity of universal hashing
• On the optimal time/space tradeoff for hash tables
• scientific article; zbMATH DE number 1962820
• Space efficient hash tables with worst case constant access time
• scientific article; zbMATH DE number 1418345
• A unified approach to linear probing hashing
• scientific article; zbMATH DE number 1688373
• Combinatorial techniques for universal hashing
• On Universal Classes of Extremely Random Constant-Time Hash Functions

Cited in

(37)

• The computational complexity of universal hashing
• Structural results on matching estimation with applications to streaming
• Unique permutation hashing
• PSI from PaXoS: fast, malicious private set intersection
• Efficient sampling of non-strict turnstile data streams
• Algorithms for projecting points to give the most uniform distribution with applications to hashing
• More analysis of double hashing
• Hardness-preserving reductions via cuckoo hashing
• Quantum key distribution with PRF(Hash, Nonce) achieves everlasting security
• Efficient set intersection with simulation-based security
• Balls and bins: smaller hash families and faster evaluation
• Sorting and Permuting without Bank Conflicts on GPUs
• Tight Bounds for Hashing Block Sources
• Uniform hashing in constant time and linear space
• Optimal hashing
• scientific article; zbMATH DE number 177800 (Why is no real title available?)
• On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• The Tree Model for Hashing: Lower and Upper Bounds
• scientific article; zbMATH DE number 7375961 (Why is no real title available?)
• When Simple Hash Functions Suffice
• Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations
• Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions
• Algorithmic aspects in speech recognition
• Space/time trade-offs in hash coding with allowable errors
• Tight tradeoffs in searchable symmetric encryption
• Cuckoo hashing in cryptography: optimal parameters, robustness and applications
• Bet-or-pass: adversarially robust Bloom filters
• On the impossibility of ``succinct automata representation of hash functions
• Tiny pointers
• ShockHash: near optimal-space minimal perfect hashing beyond brute-force
• Iceberg hashing: optimizing many hash-table criteria at once
• Everlasting anonymous rate-limited tokens
• MorphisHash: improving space efficiency of ShockHash for minimal perfect hashing
• Combined search and encoding for seeds, with an application to minimal perfect hashing
• Analysis of parallel uniform hashing
• Universal hash functions for an infinite universe and hash trees

This page was built for publication: Uniform Hashing in Constant Time and Optimal Space

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