Linear Hashing is Not That Awesome
2026-08-24 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors explore a common method for hashing called linear hashing, which spreads items into buckets using simple math formulas. They show that, contrary to hopes, the largest bucket can still be quite big and does not shrink to very small sizes as the number of items grows. They also apply these findings to a related hashing method called multiply-shift hashing. By connecting this problem to a special kind of math question involving arithmetic progressions, the authors reveal that improving known limits is as hard as solving deep problems in number theory.
universal hashinglinear hashingmaximum loadmultiply-shift hasharithmetic progressionsKakeya setsdensityhash functionsarithmetic combinatoricsGreen-Ruzsa construction
Authors
Or Zamir
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=Θ(n)$ buckets. For any universal family, the expected size of the largest bucket is at least $Ω(\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^{Ω(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.