Bloom Filter

Probabilistic data structure used like a set that provides:

  • No false negatives
  • Low false positive rate

What’s a bloom filter?

Simply put, a bit vector of N bits, and a set of K hash functions.

Set operations

Insertion

To insert a value X into a Bloom filter, simply hash it over each one of the K hash functions, and treating the hash outputs as indices into the bit-vector, raise the corresponding bits.

Query

To query for a value X in the Bloom filter, once again hash it over each one o f the K hash functions, and then check whether all of the corresponding bits are raised.

Source

https://gopiandcode.uk/logs/log-bloomfilters-debunked.html