Bloom Filters
A Bloom Filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set.
1. The Core Concept
It tells you one of two things:
- The element is definitely not in the set.
- The element is probably in the set.
It never returns a false negative (if it says "no", it means "no"), but it can return a false positive (it might say "yes" when the answer is actually "no").
2. How it Works
A Bloom filter is essentially a bit array of $m$ bits, all initially set to 0.
Adding an Element
To add an element:
- Feed it to $k$ different hash functions.
- Each function returns an index position.
- Set the bits at those positions to 1.
Checking for an Element
To check if an element exists:
- Feed it to the same $k$ hash functions to get the index positions.
- Check the bits at those positions.
- If any bit is 0: The element is definitely not in the set.
- If all bits are 1: The element is probably in the set.
3. Why "Probably"? (False Positives)
It's possible that other elements just happened to set those specific bits to 1. This is a collision. As the filter fills up (more bits become 1), the probability of false positives increases.
4. Pros and Cons
- Pros: Extremely space-efficient (much smaller than a Hash Table) and fast ($O(k)$).
- Cons: Can't remove items (standard Bloom Filter), and allows false positives.
5. Use Cases
- Databases: To quickly check if a row exists on disk before doing an expensive disk read (e.g., Cassandra, HBase).
- Web Browsers: Checking if a URL is in a list of known malicious sites.
- CDNs: To avoid caching "one-hit wonders" (only cache if seen twice).
programming/hash-tables programming/algorithms programming/caching-strategies