2012/01/01 by Mikkel Thorup, Yin Zhang⋆ · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Coding theory and cryptography #Advanced Data Storage Technologies #Hash function #Double hashing #Computer science #Universal hashing #Function (biology) #Rolling hash #Hash table #Dynamic perfect hashing #Perfect hash function #Algorithm #Theoretical computer science #Moment (physics) #Polynomial #Mathematics #Discrete mathematics
paper · doi:10.1137/100800774
openalex publication_date 2012/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
In the framework of Wegman and Carter, a k-independent hash function maps any k keys independently. It is known that 5-independent hashing provides good expected performance in applications such as linear probing and second moment estimation for data streams. The classic 5-independent hash function evaluates a degree 4 polynomial over a prime field containing the key domain [n]=\0,…,n-1\. Here we present an efficient 5-independent hash function that uses no multiplications. Instead, for any parameter c, we make 2c-1 lookups in tables of size O(n1/c). In experiments on different computers, our scheme gained factors of 1.8 to 10 in speed over the polynomial method. We also conducted experiments on the performance of hash functions inside the above applications. In particular, we give realistic examples of inputs that make the most popular 2-independent hash function perform quite poorly. This illustrates the advantage of using schemes with provably good expected performance for all inputs.