Some thoughts on hashing

I was looking for fast hash algorithms and I found Paul Hsieh SuperFastHash implementation. I also found that hash functions in Bloom filter algorithm are used to test if an element is member of a set.

I found interesting fact, that it's possible to count any number of independent hashes using only two hash functions using this formula (f1 and f2 are hash functions, i is any number that is relatively prime to m):

Even more surprising is fact that if f1 is something like this:
than f2 can be:
Which means, that to count any number of hash functions for specified element, it's needed to count only one "real" hash(x), plus some additional sums and modulos.

Knuth suggests to use such m value, that both m and m-2 are primes, like 1021 and 1019.

No comments: