Paper Info
Title
Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation
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.
Year
DOI
Venue
2012
10.1137/100800774
SIAM J. Comput.
Keywords
Field
DocType
independent hash function map,hash function,5-independent hash function,2-independent hash function,different computer,independent hash function,Second Moment Estimation,5-Independent Hashing,good expected performance,data stream,provably good expected performance,polynomial method
Discrete mathematics,Linear probing,Hash function,Table (information),Mathematics,Second moment of area
Journal
Volume
Issue
ISSN
41
2
0097-5397
Citations 
PageRank 
References 
32
1.20
26
Authors
2
Name
Order
Citations
PageRank
Mikkel Thorup15081366.30
Yin Zhang23492281.04