Linear Hashing Is Optimal

We prove that hashing n balls into n bins via a random matrix over 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 • log n/ log log n with probability at most O(1/r 2 ).