Maximum-load problem for linear hashing

The problem asks for the worst expected largest bucket under affine modular hashing when the universe is nearly linear in the number of keys. No complete asymptotic formula is known.

Known results

• Green and Ruzsa: lower bound $\Omega\!\left(\frac{\log n}{\log\log n}\right)$.
• Knudsen: upper bound $\widetilde{O}(n^{1/3})$.
• Dhar and Dvir, 2024: near-uniform loads for a related finite-field random-linear-map setting.

August 2026 lower-bound advance

The preprint Lower Bounds for Linear Hashing via Arithmetic Kakeya claims, for universes of size $n^{1+o(1)}$, a substantially stronger lower bound, including a key set attaining the load for every random seed. It also shows that a uniform subpolynomial upper bound would imply new arithmetic-Kakeya bounds. The related preprint Linear Hashing is Not That Awesome gives the scale $n^{\Omega(1/\log\log n)}$ in a stated prime-modulus range. These claims are unverified and do not determine the asymptotic growth.

Current status (as of August 2026): A stronger lower bound is claimed for the near-linear-universe regime, but it is unverified, and the gap between $n^{\Omega(1/\log\log n)}$ and $\widetilde{O}(n^{1/3})$ remains open.