Bloom Filter

Probabilistic data structure for testing set membership.

Bloom filters

A Bloom filter is a probabilistic data structure that tests whether an element is a member of a set. It can definitively tell you an element *is not* in the set, but may occasionally return a false positive (indicating an element *might* be present when it isn't). It uses bit arrays and multiple hash functions to achieve this with space efficiency.

Bloom filter is named after Burton Bloom, who described it in 1970.

probabilistic data structure

bit array hash function

algorithm data storage data structure