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

randomized algorithmshash functionuniform hashing

Mathematics Subject Classification ID

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

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
• Publication:4941908
• 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

(27)

• 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
• Uniform hashing in constant time and linear space
• Sorting and Permuting without Bank Conflicts on GPUs
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Balls and bins: smaller hash families and faster evaluation
• Efficient set intersection with simulation-based security
• When Simple Hash Functions Suffice
• Cuckoo hashing in cryptography: optimal parameters, robustness and applications
• Quantum key distribution with PRF(Hash, Nonce) achieves everlasting security
• Space/time trade-offs in hash coding with allowable errors
• Universal hash functions for an infinite universe and hash trees
• scientific article; zbMATH DE number 7375961 (Why is no real title available?)
• Structural results on matching estimation with applications to streaming
• Efficient sampling of non-strict turnstile data streams
• Tight Bounds for Hashing Block Sources
• Bet-or-pass: adversarially robust Bloom filters
• Tight tradeoffs in searchable symmetric encryption
• The computational complexity of universal hashing
• Analysis of parallel uniform hashing
• Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations
• PSI from PaXoS: fast, malicious private set intersection
• Unique permutation hashing
• Hardness-preserving reductions via cuckoo hashing
• Algorithmic aspects in speech recognition
• Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions
• Optimal hashing

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)