Linear Hashing Is Optimal

We prove that hashing $n$ balls into $n$ bins via a random matrix over ${\mathbf{F}}_2$ yields expected maximum load $O(\log n\mathrm{/}\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\mathrm{/}\log \log n$ with probability at most $O(1\mathrm{/}{r}^2)$.