Linear Hashing Is Optimal

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)$.

20 pages, 1 figure; to appear in STOC 2025