Linear Hashing is Not That Awesome

Abstract

Consider the canonical universal hash family $h(x)=((ax+b)\text{ mod }p)\text{ mod }m$, where $a,b$ are chosen uniformly from ${\mathbb{Z}}_p$, which we call linear hashing, being used to hash $n$ elements into $m=\Theta (n)$ buckets. For any universal family, the expected size of the largest bucket is at least $\Omega (\log n/\log \log n)$ and at most $O(\sqrt{n})$. The only improvement upon these trivial bounds for linear hashing is a 2019 upper bound of $\tilde{O}(n^{1/3})$ by Knudsen. We show that for any $p$ sufficiently larger than $n$, there is a set of $n$ keys whose expected maximum load is $n^{\Omega (1/\log \log n)}$, proving linear hashing does not have a polylogarithmic maximum load. We extend the same bounds to the classical multiply-shift hash family of Dietzfelbinger, Hagerup, Katajainen, and Penttonen. We prove an equivalence between the maximum load problem to a density variant of arithmetic Kakeya sets. We then complete the lower bound using a construction of Green and Ruzsa of a small set containing long arithmetic progressions with every difference in a prescribed range. Surprisingly, our equivalence also implies that any substantial improvement over Knudsen's upper bound would imply new results about standard arithmetic Kakeya sets.