preprint · ArXiv.org · 2025

Linear Hashing Is Optimal

Michael Jaber, Vinayak M. Kumar, David Zuckerman

Cited by 0Open access

Abstract

We prove that hashing $n$ balls into $n$ bins via a random matrix over $\mathbf{F}_2$ yields expected maximum load $O(\log n / \log \log n)$. This matches the expected maximum load of a fully random function and resolves an open question posed by Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos (STOC '97, JACM '99). More generally, we show that the maximum load exceeds $r\cdot\log n/\log\log n$ with probability at most $O(1/r^2)$.

Cite this paper

APA 7

Jaber, M., Kumar, V. M., & Zuckerman, D. (2025). Linear Hashing Is Optimal. ArXiv.org. https://doi.org/10.48550/arxiv.2505.14061

MLA 9

Jaber, Michael, et al. “Linear Hashing Is Optimal.” ArXiv.org, 2025, https://doi.org/10.48550/arxiv.2505.14061.

Chicago

Jaber, Michael, Vinayak M. Kumar, and David Zuckerman. 2025. “Linear Hashing Is Optimal.” ArXiv.org. https://doi.org/10.48550/arxiv.2505.14061.

Harvard

Jaber, M., Kumar, V.M. and Zuckerman, D. (2025) ‘Linear Hashing Is Optimal’, ArXiv.org. Available at: https://doi.org/10.48550/arxiv.2505.14061.

BibTeX

@misc{jaber2025linear,
  title = {{Linear Hashing Is Optimal}},
  author = {Jaber, Michael and Kumar, Vinayak M. and Zuckerman, David},
  journal = {ArXiv.org},
  year = {2025},
  doi = {10.48550/arxiv.2505.14061}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.