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:
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.
Related Resources
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).
For additional information on related topics, take a look at the following resources:
- Common Python Data Structures (Guide) (Tutorial)
- Sets in Python (Tutorial)
- Using Sets in Python (Course)
- Bitwise Operators in Python (Tutorial)
- Build a Hash Table in Python With TDD (Quiz)
- Records and Sets: Selecting the Ideal Data Structure (Course)
- Stacks and Queues: Selecting the Ideal Data Structure (Course)
- Dictionaries and Arrays: Selecting the Ideal Data Structure (Course)
- Common Python Data Structures (Guide) (Quiz)
- Python Sets (Quiz)
- Binary, Bytes, and Bitwise Operators in Python (Course)
- Bitwise Operators in Python (Quiz)
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