Uniform Hashing in Constant Time and Optimal Space

DOI10.1137/060658400zbMath1165.68027OpenAlexW2008159385MaRDI QIDQ3614151

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

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

Related Items (16)

Efficient set intersection with simulation-based security ⋮ Sorting and Permuting without Bank Conflicts on GPUs ⋮ Bloom Filters in Adversarial Environments ⋮ Triangle counting in dynamic graph streams ⋮ Hardness-preserving reductions via cuckoo hashing ⋮ Cuckoo hashing in cryptography: optimal parameters, robustness and applications ⋮ Unnamed Item ⋮ Bet-or-pass: adversarially robust Bloom filters ⋮ Quantum key distribution with PRF(Hash, Nonce) achieves everlasting security ⋮ On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes ⋮ Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations ⋮ Structural results on matching estimation with applications to streaming ⋮ Tight tradeoffs in searchable symmetric encryption ⋮ Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions ⋮ Efficient sampling of non-strict turnstile data streams ⋮ PSI from PaXoS: fast, malicious private set intersection

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