AI summaryⓘ
The authors study a simple hashing method called affine modular linear hashing, which assigns keys to bins using arithmetic operations modulo a prime number. Although this method is straightforward, how unevenly keys can be distributed (maximum load) was not well understood. They prove a new, much stronger lower bound on the maximum load for large key sets, showing that in some cases the load is very large for every choice of random parameters. The authors connect this problem to advanced mathematical objects called Kakeya sets, revealing deep links between hashing performance and unsolved problems in geometry. They also provide insights that unify related hashing methods and suggest that improving upper bounds would solve long-standing conjectures in mathematics.
affine modular linear hashingmaximum loadhash functionsmodular arithmeticKakeya setarithmetic Kakeya conjectureupper Minkowski dimensionprobabilistic methodhashing upper boundhashing lower bound
Authors
Ainesh Bakshi, Alex Conway, Hanna Komlós, William Kuszmaul, Alek Westover
Abstract
Affine modular linear hashing is one of the simplest classical hash families. For a prime $p > u$, the hash function is obtained by choosing $s,t$ uniformly from $\mathbb{Z}_p$ and mapping each key $x \in \{0,\ldots,u-1\}$ to one of $n$ bins by $h(x) = [(sx+t) \bmod p] \bmod n$. Despite its simplicity, the maximum load of linear hashing remains poorly understood. For $n$ keys hashed into $n$ bins, the best known upper bound is $O((n \log n)^{1/3})$, whereas the best known lower bound is only $Ω(\log n / \log\log n)$. We prove a lower bound of $\exp(Ω(\log n / \log\log n))$ for universes of size $n^{1+o(1)}$. Surprisingly, there is a key set for which this load holds not just in expectation, but for every random seed. The proof is driven by two simple reductions: one transfers lower bounds from a real version of linear hashing to modular linear hashing, and the other transfers arithmetic Kakeya constructions to real hashing. We further show that, for sufficiently large $p$, the expected maximum loads in the modular and real settings are essentially the same, giving an alternative route to an $n^{1/3+o(1)}$ upper bound. Finally, we show that any uniform subpolynomial upper bound for either setting would imply a polynomial-length arithmetic Kakeya conjecture and hence the Kakeya conjecture for upper Minkowski dimension.