Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation
Authors:
- Mikkel ThorupMTMikkel Thorup
- Yin ZhangYZYin Zhang
- 1 January 2012
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 41 (2) , 293-331
Abstract
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,\ldots,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(n^{1/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.
Keywords
This publication has 23 references indexed in Scilit:
- Linear Probing with Constant IndependenceSIAM Journal on Computing, 2009
- Data Streams: Algorithms and ApplicationsFoundations and Trends® in Theoretical Computer Science, 2005
- On Universal Classes of Extremely Random Constant-Time Hash FunctionsSIAM Journal on Computing, 2004
- The Space Complexity of Approximating the Frequency MomentsJournal of Computer and System Sciences, 1999
- A Reliable Randomized Algorithm for the Closest-Pair ProblemJournal of Algorithms, 1997
- Effective erasure codes for reliable computer communication protocolsACM SIGCOMM Computer Communication Review, 1997
- Randomized algorithms and pseudorandom numbersJournal of the ACM, 1993
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- Schnelle Multiplikation großer ZahlenComputing, 1971
- Algorithm 64: QuicksortCommunications of the ACM, 1961