Create an animated lesson
On requestThis article is free to read. Creating a lesson uses your daily or stored credits; review the language and settings before starting.
What is a Bloom filter?
TechnologyLesson on requestFree to read
Quick answer
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.
Key things to understand
- It stores a bit array; each item is hashed by several functions that flip bits on.
- To check membership it tests those bits — all on means 'maybe present,' any off means 'definitely absent.'
- It can say 'maybe' wrongly (a false positive) but is never wrong about 'absent.'
- It can't store the items themselves or, in the basic version, delete them.
- Used by databases, web caches, and browsers to skip expensive lookups for items that aren't there.
People also ask
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.