Bloom Filter - Probabilistic Data Structure

What is a Bloom Filter?

A Bloom Filter is a space-efficient probabilistic data structure designed to test whether an element is a member of a set. It answers the question "Is this item in the set?" with one of two possible answers:

• "Definitely NOT in the set" — this answer is always 100% correct
• "Probably in the set" — this might be wrong (false positive)

The key trade-off is that Bloom filters use dramatically less memory than storing all elements explicitly, at the cost of occasional false positives. They never produce false negatives — if the filter says an element is not present, you can trust that completely.

Why does this matter? Imagine checking if a username is taken before allowing registration. With millions of usernames, storing them all in memory is expensive. A Bloom filter can tell you "this username is definitely available" (no false negatives) or "this username might be taken, check the database to be sure" (possible false positive). The vast majority of checks avoid the expensive database query entirely.

Python Implementation

Optimal Parameters

The math behind choosing the right size and number of hash functions:

Where: n = expected number of elements, p = desired false positive rate, m = bits, k = hash functions.

Practical example: For 1 million items with 1% false positive rate:

• Bit array size: ~9.6 million bits ≈ 1.2 MB
• Number of hash functions: 7
• Compare: Storing 1 million strings averages 20-50 MB

Complexity Analysis

Since k is a small constant (typically 3-10), all operations are effectively O(1).

Limitations and Solutions

Real-World Applications

1. Google Chrome — checks URLs against a Bloom filter of known malicious sites before making an expensive server request
2. Apache Cassandra/HBase — uses Bloom filters to avoid disk reads for keys that do not exist in an SSTable
3. Bitcoin — SPV (Simplified Payment Verification) nodes use Bloom filters to request relevant transactions
4. Medium — uses Bloom filters to avoid recommending articles a user has already read
5. Akamai CDN — avoids caching one-hit-wonder URLs using a Bloom filter (only cache on second request)
6. Spell checkers — quickly determine if a word might be misspelled before expensive dictionary lookup

Interview Questions

Q1: Can Bloom filters have false negatives? A: No. If the filter says "not in set", it is guaranteed correct. Bits can only be set to 1, never back to 0. If any required bit is 0, the element was never inserted.

Q2: How do you reduce the false positive rate? A: Increase bit array size (m) for more space between hash positions, or adjust the number of hash functions (k) to the optimal value. The optimal k = (m/n) × ln(2).

Q3: Can you remove elements from a Bloom filter? A: Not from a standard Bloom filter — unsetting a bit might affect other elements that hash to the same position. Use a Counting Bloom Filter that stores counters (typically 4-bit) instead of single bits, allowing decrement on deletion.

Q4: How is a Bloom filter different from a hash table? A: A hash table stores actual key-value pairs and has zero false positives but uses much more memory. A Bloom filter stores no actual data — only bits — using far less memory but accepting a small false positive rate. Bloom filters cannot retrieve values, only test membership.

Q5: What is a Scalable Bloom Filter? A: When the expected number of items is unknown, a Scalable Bloom Filter creates additional filter layers as needed, each with a tighter false positive rate, maintaining the overall target error rate as the set grows.