Which hash functions to use in a Bloom filter

function hash bloom-filter
Torsten picture Torsten · Aug 14, 2012 · Viewed 13.3k times · Source

I've got the following question about choosing hash functions for Bloom filters:

  • Which functions to use?

In nearly every document/paper you can read that the hash functions used in a Bloom filter should be independent and uniformly distributed.

I know what is meant by this (independent and uniformly distributed), but I'm having trouble to find a argumentation or a discussion, which hash functions fulfill those requirements and are therefore suitable. In a lot of posts I've read about suggestions for the usage of the FNV or Murmur hash function, but not why (or at least without a proof) they are suitable.

Thanks in advance!

Answer

DivineTraube picture DivineTraube · Oct 31, 2016

I asked myself the same question when building a Java Bloom filter library. See the Github readme for a detailed treatment of my analysis of hash functions for Bloom filters.

I looked at the problem from two perspectives:

  • How fast is the computation?
  • How uniform is the output distribution?

Speed can easily be measured by benchmarks on random input. Uniformity is a bit harder and requires some statistics. Using Chi-Square goodness of fit tests I measured how similar the distribution of hash values is to a uniform distribution.

The result is:

  • Use Murmur3 for the best trade-off between speed and uniformity. Do not use Murmur2 as it is not uniform for inputs that change in small increments.
  • Use a cryptographic hash function like SHA-256 for the best uniformity.
  • Apply the Kirsch-Mitzenmacher-Optimization to only compute 2 instead of k hash functions (hash_i = hash1 + i x hash2).

If your implementation is using Java I would recommend using our Bloom filter hash library. It is well documented and thoroughly tested. For the details, including the benchmark results for different hash function and their unformity according to Chi-Square test, see the Github readme of the repo.

Related questions

How do you create a callback function (dispatch table) in Perl using hashes?

I want to call a main controller function that dispatches other function dynamically, something like this: package Controller; my %callback_funcs = (); sub register_callback{ my ($class,$callback,$options) = _@; #apppend to %callback_funcs hash ... ? } sub main{ %callback_funcs = ( add => 'add_…

Read More
How do JavaScript closures work?

How would you explain JavaScript closures to someone with a knowledge of the concepts they consist of (for example functions, variables and the like), but does not understand closures themselves? I have seen the Scheme example given on Wikipedia, but …

Read More
Set a default parameter value for a JavaScript function

I would like a JavaScript function to have optional arguments which I set a default on, which get used if the value isn't defined (and ignored if the value is passed). In Ruby you can do it like this: def …

Read More