Linear Hashing Is Awesome
Knudsen Mathias Bæk Tejs. Arxiv 2017
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].
Similar Work