Lower Bounds for Linear Hashing via Arithmetic Kakeya

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 Z_p and mapping each key x ∈ {0, ..., u - 1} to one of n bins by

 

h_mod(s,t)(x) := ((sx + t) mod p) mod 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. This lower bound derives from 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.