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.
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.
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.