Bloom Filters by Example (2013)

Bloom Filters by Example (2013)

To add an element to the Bloom filter, we simply hash it a few times and set the bits in the bit vector at the index of those hashes to 1. In the following text, we will refer to a Bloom filter with k hashes, m bits in the filter, and n elements that have been inserted. Your false positive rate will be approximately (1-e-kn/m)k, so you can just plug the number n of elements you expect to insert, and try various values of k and m to configure your filter for your application.2

This leads to an obvious question:

The more hash functions you have, the slower your bloom filter, and the quicker it fills up.

Source: llimllib.github.io