Alek Westover

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 $\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 o...