A Bloom filter is a space-efficient probabilistic data structure that tests whether an element is a member of a set. False positives are possible, but false negatives are not. Watch how hash functions map elements to a bit array and see when false positives occur.
Why use a Bloom filter?
Bloom filters use far less memory than storing actual elements. Perfect for checking if a username exists, if a URL is malicious, or if data is in cache—before doing expensive lookups.
How it works
Elements are hashed by multiple hash functions, each setting bits in a bit array. To check membership, hash the element and verify all corresponding bits are set. If any bit is 0, the element is definitely not in the set.
Good for
- Cache lookup optimization in databases
- Malicious URL detection in browsers
- Spell checkers and dictionary lookups
- Avoiding expensive disk reads in distributed systems
Questions people ask
Can Bloom filters have false negatives?
No, Bloom filters never have false negatives. If the filter says an element is not present, it definitely is not. However, false positives are possible.
How do I reduce false positives?
Use a larger bit array or more hash functions. The false positive rate decreases exponentially with array size and is optimized when the number of hash functions is around ln(2) × (m/n).