Uniform Hashing in Constant Time and Optimal Space
From MaRDI portal
Publication:3614151
DOI10.1137/060658400zbMATH Open1165.68027OpenAlexW2008159385MaRDI QIDQ3614151FDOQ3614151
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
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
Information storage and retrieval of data (68P20) Data structures (68P05) Searching and sorting (68P10)
Cited In (26)
- 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
- Cuckoo hashing in cryptography: optimal parameters, robustness and applications
- Space/time trade-offs in hash coding with allowable errors
- Quantum key distribution with PRF(Hash, Nonce) achieves everlasting security
- Universal hash functions for an infinite universe and hash trees
- Title not available (Why is that?)
- 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
- Algorithmic aspects in speech recognition
- Hardness-preserving reductions via cuckoo hashing
- Unique permutation hashing
- Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions
- Optimal hashing
- Title not available (Why is that?)
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)
