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