The Power of Simple Tabulation Hashing

DOI10.1145/2220357.2220361zbMath1281.68089arXiv1011.5200OpenAlexW2129930407WikidataQ21994406 ScholiaQ21994406MaRDI QIDQ5395685

Mihai Pǎtraşcu, Mikkel Thorup

Publication date: 17 February 2014

Published in: Journal of the ACM, Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.5200

zbMATH Keywords

independencehashinglinear probingtabulationcuckoo hashingconcentration boundsminwise independencetabulation hashing

Mathematics Subject Classification ID

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

Related Items (12)

Efficient set intersection with simulation-based security ⋮ Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence ⋮ Triangle counting in dynamic graph streams ⋮ d-k-min-wise independent family of hash functions ⋮ Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8 ⋮ Simple, compact and robust approximate string dictionary ⋮ Hardness-preserving reductions via cuckoo hashing ⋮ Cuckoo hashing in cryptography: optimal parameters, robustness and applications ⋮ Unnamed Item ⋮ Explicit and efficient hash families suffice for cuckoo hashing with a stash ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: The Power of Simple Tabulation Hashing