A Bloom filter answers one question — "have I seen this before?" — using a tiny bit array and no stored keys at all. Adding an item flips k bits chosen by k hashes. To check membership, look at those same k bits: if any is 0, the item is definitely not in the set; if all are 1, it's probably in — probably, because other items may have set those bits. It can give a false yes, but never a false no. Add a few items, then go hunting for a false positive.
m bits, all starting at 0. The entire data structure — no keys are ever stored.
k hashes
Each item maps to k bit positions via k independent hash functions.
add
Set all k of the item’s bits to 1.
query
Any of the k bits is 0 → definitely absent. All 1 → probably present.
bloom.js — k hashes, m bits, no keys
Ready
A bit array of 24 bits, all zero. Each item is hashed by k=3 functions to three bit positions. Add item sets those bits; Query checks them.
0
items added
0/24
bits set
0%
est. FP rate
How it works
The magic is the asymmetry of the error. A "no" is always trustworthy: if even one of the item's k bits is 0, then this item was never added, because adding it would have set that bit. A "yes" is only probable: all k bits being 1 could be a coincidence — other items may have set exactly those bits. So the filter is a fast, tiny pre-check that can rule things out with certainty and rule them in only with high probability.
1
Start with all zeros
The bit array holds only bits — never the items themselves. That’s why it’s so small: it doesn’t store keys.
2
Add: light k bits
Run the item through k hashes to get k positions, and set all of them to 1. Bits may already be set by other items — that’s fine, and it’s the source of collisions.
3
Query: check k bits
Look at the item’s k positions. Any 0 means it was definitely never added. All 1 means probably added — but maybe those bits were set by others.
✓
Tune the false-positive rate
More bits (larger m) or more items (larger n) change the fill. The false-positive rate is about (1 − e^(−kn/m))^k — pick m and k for your target.
Add / query
O(k)
Space
O(m) bits
False negatives
Never
False positives
Tunable
The code
# m bits, k hash functions. No keys are ever stored.class BloomFilter:
def __init__(self, m, k):
self.m, self.k = m, k
self.bits = [0] * m
def add(self, item):
for i in range(self.k):
self.bits[hash_i(item, i) % self.m] = 1 # light k bitsdef __contains__(self, item):
for i in range(self.k):
if self.bits[hash_i(item, i) % self.m] == 0:
return False # a 0 bit => DEFINITELY absentreturn True # all 1 => PROBABLY present
Quick check
1. A Bloom filter says an item is "not present". How sure can you be?
A "no" is definitive. If any of the item’s k bits is 0, the item was never added — because adding it would have set that bit. Bloom filters have no false negatives.
2. It says an item IS present. What does that mean?
A "yes" is only probabilistic. All k bits being 1 could be a coincidence caused by other added items setting exactly those positions — a false positive. Never a false negative, sometimes a false positive.
3. Why is a Bloom filter so space-efficient?
It never stores the items — only a bit array. That’s the trade: you give up the ability to list members or delete safely, in exchange for tiny, constant-size membership checks.
FAQ
What is a Bloom filter?
A space-efficient probabilistic data structure for set membership. It uses a bit array and k hash functions: adding sets k bits, querying checks them. It can return false positives but never false negatives.
Why can a Bloom filter have false positives but not false negatives?
Adding only ever sets bits, never clears them. So a truly-added item always has all k bits at 1 — a query can’t miss it (no false negatives). But those bits may also be 1 from other items, so a never-added item can read as present (false positive).
Can you delete from a Bloom filter?
Not from a standard one — clearing a bit might break another item that shares it, causing false negatives. A counting Bloom filter uses small counters instead of bits to allow deletion, at the cost of more space.
Where are Bloom filters used?
As a fast pre-check to skip expensive work: LSM-tree databases (Cassandra, Bigtable) use them to avoid disk reads for absent keys; browsers/CDNs for malicious-URL checks; crawlers to skip seen URLs. Anywhere a cheap "definitely not here" saves an expensive lookup.