Linear Hashing Is Optimal

We prove that hashing n balls into n bins via random 2 -linear maps yields expected maximum load O (log n / loglog n ), resolving an open question of Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos (STOC ’97, JACM ’99). More generally, we show that the maximum load exceeds r · log n /loglog n with probability at most O (1/ r 2 ). Our proof uses potential functions to detect heavy bins.

Authors

• Michael Jaber
• Vinayak M. Kumar
• David Zuckerman

Keywords

• balls and bins
• pseudorandomness
• universal hash functions