Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation

TY - JOUR

T1 - Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation

AU - Thorup, Mikkel

AU - Zhang, Yin

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1137/100800774

DO - 10.1137/100800774

M3 - Journal article

SN - 0097-5397

VL - 41

SP - 293

EP - 331

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -