Linear Hashing Is Awesome

Knudsen Mathias Bæk Tejs. Arxiv 2017

[Paper]    
ARXIV Independent

We consider the hash function $h(x)=((ax+b)modp)modn$ 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].

Similar Work

• Optimal Lower Bounds For Locality Sensitive Hashing (except When Q Is Tiny)
• Non-empty Bins With Simple Tabulation Hashing
• Set Similarity Search Beyond Minhash
• Entropy Based Nearest Neighbor Search In High Dimensions