Bloom Filter Basics
Bloom filters are probabilistic data structures that provide space-efficient storage of elements at the cost of occasional false positives on membership queries, i.e. a bloom filter may state true on query when it in fact does not contain said element. A bloom filter is traditionally implemented as an array of
Mis the size of the bloom filter. On initialization all bits are set to zero. A filter is also parameterized by a constant
kthat defines the number of hash functions used to set and test bits in the filter. Each hash function should output one index in
M. When inserting an element
xinto the filter, the bits in the
h1(x), h2(x), ..., hk(X)are set.