Linear Hashing is Awesome

2017/06/08 by Mathias Bæk Tejs Knudsen, Knudsen, Mathias Bæk Tejs · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1706.02783

openalex publication_date 2017/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Cited by

• k-SUM Hardness Implies Treewidth-SETH

Related

• Linear Hashing Is Optimal
• On the Relationship Between Several Variants of the Linear Hashing Conjecture
• Locally Uniform Hashing
• Probabilistic behavior of hash tables
• Approximately Minwise Independence with Twisted Tabulation