  We consider the hash function $h(x) = ((ax+b) \bmod p) \bmod n$ where $a,b$
are chosen uniformly at random from $\{0,1,\ldots,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].

Data Structures and Algorithms