Skip to content

bloom filter

A Bloom filter is a probabilistic data structure that tests whether an element belongs to a set, answering either “possibly present” or “definitely absent” while using far less memory than storing the elements themselves.

The structure is a bit array of m bits, all starting at zero, paired with k independent hash functions. Adding an element runs it through each function to get k array positions and sets those bits to one. A lookup hashes the query the same way. If any of its bits is zero, the element was never added. If all of them are one, it was probably added, but other elements might have set those bits.

So the filter can return false positives but never false negatives. For n stored elements, the false-positive rate is roughly (1 - e^(-kn/m))^k, and it’s lowest when k is about (m/n) ln 2. At that setting, a 1 percent error rate costs about 9.6 bits per element, no matter how large the elements are.

The filter below has 16 bits and three hash functions. Typing an element highlights the bits it maps to, and the default query shows a false positive:

Interactive diagram — enable JavaScript to view.

A plain Bloom filter can’t delete an element, because clearing its bits could also clear bits that other elements share. It also can’t list its contents or return stored values the way a hash table does. The counting Bloom filter variant replaces each bit with a small counter, which makes removal possible at the cost of extra memory.

Burton H. Bloom described the structure in a 1970 paper in Communications of the ACM. Today it typically guards an expensive lookup. Databases such as Google Bigtable, Apache HBase, and Apache Cassandra check a Bloom filter before reading from disk, so they can skip files that don’t hold a requested row. Akamai’s content delivery network uses one to avoid caching web objects that are requested only once.

Build a Hash Table in Python With TDD

Tutorial

Build a Hash Table in Python With TDD

In this step-by-step tutorial, you'll implement the classic hash table data structure using Python. Along the way, you'll learn how to cope with various challenges such as hash code collisions while practicing test-driven development (TDD).

intermediate algorithms data-structures

For additional information on related topics, take a look at the following resources:

Have a question about this? Mentor AI can show you examples, compare related terms, and point you to tutorials.


By Martin Breuss • Updated Nov. 9, 2026