Linear Hashing is Awesome

Abstract

We consider the hash function $h(x)=((ax+b)\mathrm{mod}p)\mathrm{mod}n$ where $a,b$ are chosen uniformly at random from $\{0,1,\dots ,p-1\}$. We prove that when we use $h(x)$ in hashing with chaining to insert $n$ elements into a table of size $n$ the expected length of the longest chain is $\tilde{O}\left(n^{1/3}\right)$. The proof also generalises to give the same bound when we use the multiply-shift hash function by Dietzfelbinger et al. [Journal of Algorithms 1997].

A preliminary version appeared at FOCS'16