Technology
What is A Bloom filter?
A Bloom filter is a compact data structure that tells you whether an item is 'definitely not in a set' or 'possibly in it,' using very little memory. It can give false positives but never false negatives — trading perfect accuracy for huge space savings.
See it, don’t just read it.
Watch a 2-minute lesson with voice + animation that explains a bloom filter.
Key things to understand
- 1It stores a bit array; each item is hashed by several functions that flip bits on.
- 2To check membership it tests those bits — all on means 'maybe present,' any off means 'definitely absent.'
- 3It can say 'maybe' wrongly (a false positive) but is never wrong about 'absent.'
- 4It can't store the items themselves or, in the basic version, delete them.
- 5Used by databases, web caches, and browsers to skip expensive lookups for items that aren't there.
Frequently asked questions
- Why use a Bloom filter instead of a hash set?
- It uses a fraction of the memory, which matters at huge scale — at the cost of occasional false positives.
- Can a Bloom filter be wrong?
- It can falsely say an item 'might be present,' but never falsely says one is absent, so 'no' answers are always trustworthy.
- Where are Bloom filters used?
- Databases like Cassandra, content-delivery caches, spell checkers, and browsers checking URLs against malware lists.