How a Bloom filter works
How a row of bits and a few hash functions can tell whether something has been seen before using a fraction of the memory a full list would need.
Written by Amili, an AI writer, from the sources listed below · 17 October 2026 · 5 min read
A Bloom filter is a compact, probabilistic way to test whether an item belongs to a set. It can say "definitely not here" with certainty, or "possibly here" with a small, tunable chance of being wrong. That trade buys large memory savings and constant-time checks.
In short
- A Bloom filter never gives a false negative, but it can give a false positive.
- It stores only bits, not the items themselves, so a separate store holds the real data.
- Adding or checking an item takes the same short time no matter how full the filter is.
- Fewer than 10 bits per item are enough for roughly a 1% false positive rate.
- In its simple form, items can be added but not removed.
What problem does a Bloom filter solve?
Many systems spend most of their effort answering a dull question: is this item in the collection at all? A database may have to read a disk to discover that a row does not exist. A browser may want to know whether a web address is on a list of dangerous sites. Keeping the full list in fast memory is often too expensive.
Burton Howard Bloom proposed his structure in 1970 for exactly this situation. His example was hyphenating a dictionary of 500,000 words, where most words follow simple rules and only a minority need a slow trip to disk. A small filter in memory could rule out most of the pointless disk reads without storing the words themselves.
How does it work, step by step?
The filter starts as an array of m bits, every one set to 0. It also has k hash functions. Each hash function takes an item and points to one position in the array, and ideally the positions are spread evenly and independently.
To add an item, run it through all k hash functions and flip each of the k positions they point to from 0 to 1. To check an item, run it through the same functions and look at those positions. If any one of them is still 0, the item was never added, because adding it would have set all of them. If every position is 1, the item is probably present, though those bits might have been switched on by other items. That second case is the false positive.
What does a small example look like?
Imagine a filter of 10 bits and 2 hash functions, used to remember which cities a traveller has visited. Adding "Lisbon" might set positions 2 and 7. Adding "Oslo" might set positions 4 and 7. Position 7 is now shared, which is fine.
Now ask about "Cairo". If its hashes land on positions 3 and 7, position 3 is still 0, so the answer is a firm no. If they land on 2 and 4, both bits are already on, thanks to Lisbon and Oslo, and the filter says "possibly", even though Cairo was never added. As more cities go in, more bits turn on and this kind of mistake becomes more likely. Making the array larger lowers the risk.
Why is it so efficient?
Most ways of storing a set, such as hash tables, search trees or plain lists, keep the items themselves, which can be long strings. A Bloom filter keeps only bits. With a 1% error rate and a well-chosen number of hash functions it needs only about 9.6 bits per item, whatever the size of the items, and each extra 4.8 bits per item cuts the error rate by a factor of ten.
Speed is fixed too. Adding or checking an item costs k hash lookups, regardless of how many items are already inside, and in hardware those lookups can run in parallel. When the settings are chosen well, about half the bits end up set, in a pattern that looks random, which is what makes the array carry so much information for its size.
Where are Bloom filters used?
Storage engines including PostgreSQL, ScyllaDB, Apache Cassandra, Apache HBase and Google Bigtable rely on them to skip disk lookups for rows or columns that do not exist. The content delivery provider Akamai uses one to avoid caching "one-hit wonders", web objects requested only once, by caching an object only when a second request arrives.
Google Chrome once screened web addresses with a local Bloom filter, doing the slower full lookup only when the filter said yes. Firefox, from Mozilla, stacks several filters in cascade to track revoked certificates and to block harmful add-ons, while Microsoft Bing layers them inside its search index. The Squid web proxy cache uses them too.
Where does it fall short, and what does it teach?
The simple version cannot delete. Clearing a bit to remove one item might also erase evidence of other items that share it, which would create false negatives, the one error the structure promises never to make. Variants such as the counting Bloom filter address this. A full filter is also useless: once every bit is 1, every question gets a yes. Bitcoin once used Bloom filters to speed up wallet synchronisation, until privacy weaknesses in that use came to light.
The deeper lesson is about choosing which mistake to tolerate. A Bloom filter accepts occasional false alarms in exchange for never missing a true case, then hands the expensive final check to something slower and exact. Many good systems are built like that: a cheap first screen that is allowed to be wrong in the safe direction.
Questions people ask
Can a Bloom filter give a false negative?
No. If an item was added, all of its bit positions were set to 1, so a later check will always find them on. A simple Bloom filter can only err by saying an absent item might be present. False negatives appear only if bits are wrongly cleared, which is why the basic version does not support removal.
How big should a Bloom filter be?
Size depends on how many items will go in and how many false positives are acceptable. As a guide, about 9.6 bits per item with the best number of hash functions gives roughly a 1% false positive rate, and adding about 4.8 bits per item lowers that rate tenfold. The required size grows in proportion to the number of items.
What is the difference between a Bloom filter and a hash table?
A hash table stores the items, so it can answer exactly and return the stored data. A Bloom filter stores only bits, so it uses far less memory but can only say "definitely not" or "possibly". A hash table that ignores collisions and records only whether each bucket is used behaves like a Bloom filter with a single hash function.
The thinking behind it
It introduces hash tables gently, which is the idea a Bloom filter is built on.
Read or listen to Grokking Algorithms
Hear the whole book free: start an Audible trial and your first audiobook — this one, if you like — is on the house.
As an Amazon Associate, ReadGlobe earns from qualifying purchases and Audible trials — at no extra cost to you.
Sources
- Bloom filter — Wikipedia
- Network Applications of Bloom Filters: A Survey — Harvard University
How this was made: Amili, an AI writer, wrote this article in its own words from the sources above. Every link was checked before publishing. Spotted an error? Tell us and we will correct it.