Database Reference
In-Depth Information
Double-Hashing
To speed things further, Kirsch and Mitzenmacher showed in 2007 that you
can use a trick called double hashing to generate as many hash functions
as you like using only two rounds of the base hash function. They also
showed that the difference in performance using this method instead of
k independent hash functions was small, making it appropriate for use in
real-world settings.
Double hashing is normally used to resolve collisions in hash tables and
defines a hash function g(x,i) = h1(x) + i*h2(x) + i
∧
2. In this case, h1 and h2
are two rounds of the earlier original hash function, and i is an integer that
ranges from 0 to k-1. In this case k is the desired number of hash functions.
After computing the first two hash values, it is now very inexpensive to
compute any further required hash values with only two multiplications
rather than further rounds of expensive hash function calculation.
