Linear Hashing Is Optimal

Michael Jaber, Vinayak M. Kumar, David Zuckerman

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…