The Problem
You have a massive list of malicious URLs — say, 500 million of them. Before letting a user visit a site, you want to check if it's on the blocklist. Storing all those URLs in a database and querying it on every browser navigation adds hundreds of milliseconds of latency and hammers your database with billions of reads per day.
The Solution: Bloom Filter
A Bloom Filter is a space-efficient structure that answers membership queries with a specific guarantee: it tells you if an element might be in a set, or is definitely not in the set.
How it Works
- Setup: Allocate a large array of bits, all initialized to
0. Choosekindependent hash functions (typically 3–7). - Adding an item: To add
"malware.com", run it through allkhash functions. Each function returns an index into the bit array. Set the bits at allkpositions to1. - Checking an item: To check
"google.com", run it through the samekhash functions to getkindices. - If the bits at all those positions are
1, the item might be in the set. - If any bit is
0, the item is definitely not in the set.
The Catch: False Positives
A Bloom Filter can produce false positives — it may claim an item is in the set when it is not. This happens when the bits for a new item were all coincidentally set to 1 by other, unrelated items added previously.
However, it will never produce a false negative — if an item was added, all its bits were set to 1, and they stay 1 forever. A query for that item will always return "might be in set."
This asymmetry is the key property: false positives are possible, false negatives are impossible.
Sizing a Bloom Filter
The false positive rate is not random — it is a deterministic function of three parameters:
- n: the number of items you expect to insert
- m: the size of the bit array (in bits)
- k: the number of hash functions
The optimal false positive rate p is approximately (1 - e^(-kn/m))^k. In practice, you work backwards: decide on an acceptable false positive rate (e.g., 1%), estimate n, and use the formula to calculate the required m. A 1% false positive rate for 1 million items requires roughly 9.6 bits per item — about 1.2 MB total. A HashSet for the same data would require hundreds of MB.
Standard Bloom Filters do not support deleting items. Setting a bit back to 0 might invalidate other items that share that bit position.
Interviewers frequently ask: "Can you delete from a Bloom Filter?" The correct answer is: "Not from a standard Bloom Filter, because bits are shared across multiple items — clearing a bit for one item could cause false negatives for others. The solution is a Counting Bloom Filter, which replaces each bit with a small integer counter. Increment on add, decrement on delete. This supports deletion at the cost of more memory (typically 4x). Alternatively, Cuckoo Filters support deletion natively and are often more space-efficient."