A bloom filter is a small, compact structure that answers one question very quickly: is this item maybe in the set, or definitely not? It doesn't store the items themselves. It keeps a short row of bits and uses hash functions to decide which bits to check.
In this guide we'll build one from scratch with a tiny eight-bit example, add two usernames, and then check two more. Along the way you'll see why a bloom filter's no can always be trusted, why its yes is only a hint, and where this trade pays off in real systems.
- A bloom filter tests whether an item might be in a set, using only a row of bits.
- Adding an item hashes it to a few positions and sets those bits to 1.
- If any checked bit is 0, the item is definitely not present.
- If all checked bits are 1, the item is only probably present, so you confirm it.
- A basic bloom filter can't delete items, because bits are shared.
- 0:00Intro
- 0:22Every lookup costs you something
- 1:07A filter that says maybe or no
- 1:54Trading exactness for speed and space
- 2:45Start with a row of zeros
- 3:41Adding an item flips bits on
- 4:30Any zero means definitely not
- 5:23All ones means probably present
- 6:09Checking a username at sign-up
- 6:59Quietly skipping unnecessary lookups everywhere
- 7:44Two mistakes beginners often make
- 8:36Bloom filters in six points
- 9:05A no is certain; a yes is maybe
Why do lookups get expensive?
Think about signing up for a new app. You type a username and wait for the app to tell you whether it's free. Behind that small check, the app has to look somewhere, and the bigger its list of users grows, the more work each check takes. The developer behind it faces a real question: do I really search every record, every time someone types a name?
There are two costs here. The first is slow searches: scanning a huge list on each request makes people wait and makes the server do heavy work just to answer yes or no. The second is wasted lookups. Many of those checks end with a plain no, yet each one still pays the full price of a search. If we could skip those no answers cheaply, we'd save a lot of effort.
- Slow searches: every request scans a growing list.
- Wasted lookups: many searches end in a simple no.
What is a bloom filter?
A bloom filter is a compact structure that tests whether an item might be in a set. The key word is compact. Instead of keeping a copy of every username, it keeps a small row of bits that acts like a fingerprint of the whole set. You give it an item, it checks a few of those bits, and it replies with one of two answers.
The first answer is definitely not. When the filter says an item is absent, that answer is always correct, so you're done with no second check. The second answer is maybe in the set. A maybe is only a hint, so you go and confirm it in the real data. Accepting an uncertain yes in exchange for a certain, cheap no is the whole idea.
- Never a wrong no: a 'definitely not' is always right.
- Maybe means check: confirm a 'maybe' in the real database.
Why accept a maybe instead of an exact answer?
Exact answers aren't free. To answer perfectly, you have to store every item in full, and that list grows as the set grows. Searching it takes time too. A bloom filter exists for moments when that exact answer is too costly to store and keep close at hand.
Compare the two side by side. An exact list stores everything, grows with the data, and gives perfect yes or no answers. A bloom filter stores only a row of bits, stays small and quick to check, and gives an exact no but only a probable yes. Because it's so small, it can sit in fast memory right next to the code that needs it, and every definite no skips a slow trip to storage. A small loss in certainty buys a big gain in speed.
- Less memory: small enough to keep close at hand.
- Fewer lookups: many 'no' answers never touch the database.
How a bloom filter starts: bits and hash functions
Everything starts with a row of bits, all set to zero. To keep the example easy to follow, we'll use a tiny filter of eight bits, numbered 0 to 7. Real filters are much longer, but the mechanics are the same. In the code, the filter is just a list of eight zeros, and the position numbers act as addresses.
Each slot holds only a 0 or a 1. There's no room for usernames, which is exactly why the filter stays small. A zero means nothing has ever pointed at that position, and that fact is what gives us a definite no later. The other ingredient is hash functions. Each one takes an item and turns it into a position number, and it always gives the same number for the same item.
- Bits, not items: each slot is just 0 or 1.
- Zero means unused: nothing has pointed there yet.
- Hash functions turn an item into a position number.
# an empty Bloom filter: 8 bits
bits = [0, 0, 0, 0, 0, 0, 0, 0]
# positions: 0 1 2 3 4 5 6 7How do you add an item to a bloom filter?
To add an item, run it through several hash functions and set each resulting position to 1. Our example uses three hash functions, so every item lights up three positions. Starting from all zeros, we add alice. Her three hashes land on positions 1, 4 and 6, so the row becomes 0 1 0 0 1 0 1 0.
Next we add bob. His hashes give 2, 4 and 7. Position 4 is already 1, so it simply stays 1, and the row now reads 0 1 1 0 1 0 1 1. Notice what happened: position 4 now belongs to both alice and bob, and the filter has no way of remembering who set it. Also, hashing alice again tomorrow still gives 1, 4 and 6. That consistency is what makes checking possible.
- Bits are shared: bob reused a bit alice set.
- Same item, same bits: alice always maps to 1, 4, 6.
Why does a single zero mean definitely not?
To check an item, hash it the same way and look at those positions. If any one of them is 0, the item is definitely not present. With our row at 0 1 1 0 1 0 1 1, someone asks about carol. Hash 1 points to bit 1, which is 1. Hash 2 points to bit 3, which is 0. Hash 3 points to bit 6, which is 1. The result is definitely not.
This is guaranteed. If carol had ever been added, her hashes would have set bit 3 to 1, so a zero there proves she's absent. That's why bloom filters have no false negatives. You also don't need to check every position: the moment you hit one zero, you have your answer, and the slow database never gets asked.
- No false negatives: a zero proves the item was never added.
- Stop early: one zero is enough to answer.
Why does a bloom filter give false positives?
If every checked position is 1, the filter can only say the item is probably present. A 1 tells you that some item touched that position at some point, not which item. Ask about dave, and his hashes point to bits 2, 6 and 7. All three are 1, so the filter says maybe.
But dave was never added. Those bits were set by alice and bob. This is called a false positive: the filter says maybe, yet the item isn't really there. It isn't a bug. It's the price of using so little memory, and a real lookup quickly sorts it out.
Example: checking a username at sign-up
Back to the problem we started with. The trick is where the filter lives: right in front of the database, like a quick bouncer at the door. A new user types a name, it goes to the app server, and the server asks the bloom filter first. If the answer is definitely not, the app instantly says the name is free.
Only when the filter says maybe does the server ask the user database to confirm. Fresh, unused names get a definite no straight away, so the user sees a green tick without any database search. And because a maybe never decides on its own, a false positive costs just one extra lookup, never a wrong result.
- Fast for fresh names: no storage access needed.
- Safe when unsure: a maybe still gets an exact check.
Where are bloom filters used?
The same pattern appears across computing wherever a lookup is slow and many answers are no. Databases use bloom filters to skip reading storage that can't hold a key. Web caches use them to avoid searching for things they don't have. Browsers use them to skip lookups that aren't needed.
Each case is a cheap check placed before an expensive one. If the filter says no, the expensive step never happens. One skipped lookup is tiny, but across many requests those skipped trips add up to real time saved and real load taken off servers.
Common bloom filter mistakes beginners make
Both common mistakes come from forgetting that bits are shared between items. The first is expecting certainty. False positives are built into how a bloom filter works, so treating a maybe as a final yes will eventually give wrong answers. Always confirm a maybe against the real data.
The second is trying to delete items. Suppose you remove bob by setting his bits back to zero. Position 4 returns to 0, but alice needs it too, so alice now looks absent, which breaks the no-false-negatives promise. A basic bloom filter doesn't support deletes. If items must go away, rebuild the filter from the current set instead of clearing bits by hand.
- Don't treat a maybe as a yes: confirm it.
- Don't clear bits to delete: rebuild the filter instead.
Key takeaways
- A bloom filter is a compact test that answers 'maybe in' or 'definitely not'.
- It starts as a row of zeros; adding an item hashes it and sets bits to 1.
- Any zero among the checked bits means the item is definitely not present.
- All ones means only probably present, because bits are shared.
- A basic bloom filter can't delete items; rebuild it instead.
- Its value is a cheap check that skips expensive lookups.
Frequently asked questions
Can a bloom filter give a false negative?
No. If an item was added, its hash positions were all set to 1, and a basic filter never turns them back to 0. So if any checked bit is 0, the item was never added.
What does a 'maybe' from a bloom filter mean?
It means every checked bit is 1, but those bits might have been set by other items. Treat it as a hint and confirm the answer in the real data.
Why can't you remove items from a bloom filter?
Bits are shared between items, so clearing one item's bits can erase bits another item still needs. That would make a present item look absent. The safe approach is to rebuild the filter from the current set.
Does a bloom filter store the actual data?
No. It stores only a row of bits, each a 0 or a 1. That's why it stays small enough to keep in fast memory.
When should I use a bloom filter?
It fits situations where a lookup is slow or expensive and many answers are no, such as checking whether a username is taken. Place it in front of the slow lookup so definite no answers skip the expensive step.
