A Bloom filter is a compact set that answers membership with a small, tunable false-positive rate. It can say “definitely not present” or “possibly present”, so it is used to skip expensive lookups: if the filter says no, the key is absent, and you avoid the database entirely.
Before you start
You should understand hashing and bit arrays. This article is conceptual with a sizing discussion.
Step-by-step walkthrough
Step 1: Set bits with several hashes
Insert by hashing the key with several independent hash functions and setting the corresponding bits. A lookup checks the same bits: if any is unset, the key is definitely not present; if all are set, it is possibly present because other keys may have set those bits.
Step 2: Size the filter to the rate you can tolerate
The false-positive rate falls as you add more bits per element and rises as the filter fills. Size it for the expected number of elements and the rate you accept, and remember the rate degrades as it approaches capacity. A false positive costs an unnecessary lookup; it never costs a wrong answer.
Step 3: Respect the no-deletion limit
Standard Bloom filters cannot delete, because clearing bits for one key would affect others that share them. If you need deletion, use a counting variant, or rebuild the filter periodically. This is why they fit append-only sets such as seen-cache keys or previously fetched ids.
Worked scenario
The read path consults the filter before the database.
read(key):
if bloom.mightContain(key) == false:
return NOT_FOUND # definitely absent, skip DB
else:
return db.get(key) # possibly present, verifyWalk through the example
When the filter reports false, the key is absent and the expensive lookup is skipped, which is where the savings come from. A false positive lets a lookup proceed, and the database correctly returns not found. The filter never produces a false negative, so a skip is always safe.
Common mistake
Treating “possibly present” as truth and returning a value without verifying, which would fabricate data for the false positives. Another is expecting to delete from a plain Bloom filter; deletions corrupt it.
Verify the behavior
Insert keys and assert every inserted key reports present (no false negatives). Query many absent keys and measure the false-positive rate against the configured target. Confirm a false positive only triggers a lookup and never a wrong value.
Interview exercise
Why can a Bloom filter never return a false negative?
Answer and reasoning
Inserting a key sets all of its bits, and nothing ever clears them, so a present key always has every bit set and always reports present. False positives occur because other keys may set the same bits, making an absent key look present. The asymmetry — safe skips, occasional extra lookups — is what makes the structure useful.
Continue learning
Compare caching in Cache aside and search indexes in Search indexes. Read the Bloom filter overview and try the System design interview questions.