What you'll learn
Quick Answer
A Bloom filter is a compact data structure that answers 'have I seen this before?' using far less memory than storing every item, at the cost of occasionally saying yes when the real answer is no. It never produces a false negative — if it says an item is absent, that item was genuinely never inserted — but it can produce false positives, and the rate is a number you can calculate exactly from the bit array size and the number of hash functions.
What a Bloom Filter Actually Promises
Suppose you're building a system that needs to answer one question, over and over, billions of times a day: 'have I seen this exact item before?' Maybe it's a cache deciding whether a URL is worth caching, a database deciding whether a key might exist in a file on disk before doing an expensive read, or a browser checking a URL against a list of known-malicious sites. Storing every item you've ever seen in a hash set works, but it costs memory proportional to how many items you store — and at the sizes some of these systems operate at (billions of URLs, keys, or hashes), that memory bill gets enormous.
A Bloom filter answers the same question using a fixed, tiny amount of memory that doesn't grow with the number of items beyond the initial size you pick, and it makes a very specific trade to get there: it can occasionally say 'yes, probably present' about something that was never actually inserted (a false positive), but it will never say 'no, definitely absent' about something that actually was inserted (a false negative). That asymmetry is the entire design — and it's precise enough that you can calculate the exact probability of a false positive from three numbers: how many bits you allocated, how many items you inserted, and how many hash functions you used.
This makes a Bloom filter a pre-filter, not a source of truth. A 'maybe present' result means you still need to check the real, authoritative store — the database, the file, the block list — to be sure. A 'definitely absent' result means you can skip that check entirely. The entire value of the structure comes from how often it lets you skip the expensive path.
Bits and Hash Functions: How It Works
The structure itself is almost embarrassingly simple: a bit array of some fixed length m, with every bit initialized to 0, plus a fixed number k of hash functions. To insert an item, you run it through all k hash functions, get k positions in the array (each hash function's output taken modulo m), and set the bit at each of those positions to 1. That's the whole insert operation — no linked lists, no buckets, no collision chains, just flipping some bits to 1.
To check whether an item might be present, you run it through the same k hash functions to get the same k positions, and check whether all k of those bits are currently 1. If even one of them is 0, you know for certain the item was never inserted — because inserting it would have set that exact bit to 1, and bits are never unset. If all k bits are 1, the item is 'probably present' — but you can't be certain, because those bits could have ended up as 1 purely by coincidence, from the combined hashing of other, unrelated items that happen to land on the same positions.
That coincidental overlap is exactly where false positives come from, and it's also why the structure never produces false negatives: absence of even one required bit is airtight proof of absence, while presence of all required bits is only probabilistic evidence of presence.
Building One From Scratch in Python
Here's a real implementation — a bit array (a bytearray of 0s and 1s for clarity), and k hash functions built by running SHA-256 over the item concatenated with a different seed number for each of the k hashes. Using one strong hash function with k different seeds is a completely standard, legitimate way to get k independent-enough hash functions without hand-rolling k different hashing algorithms.
class BloomFilter:
def __init__(self, size_bits, num_hashes):
self.size_bits = size_bits
self.num_hashes = num_hashes
self.bits = bytearray(size_bits)
def _hash_positions(self, item):
item_bytes = item.encode("utf-8")
positions = []
for i in range(self.num_hashes):
h = hashlib.sha256(item_bytes + b":" + str(i).encode()).hexdigest()
positions.append(int(h, 16) % self.size_bits)
return positions
def add(self, item):
for pos in self._hash_positions(item):
self.bits[pos] = 1
def might_contain(self, item):
return all(self.bits[pos] == 1 for pos in self._hash_positions(item))all(self.bits[pos] == 1 ...) is the exact 'all k bits must be 1' check described above — a single 0 anywhere is enough to return False with certainty.
The Real Experiment: Inserting 1,000 Items
To make this concrete instead of theoretical, I built a bit array of m = 5,000 bits with k = 3 hash functions, generated 1,000 random lowercase strings (4 to 10 characters each, seeded for reproducibility) as the inserted set, and inserted every one of them.
First check: does the 'no false negatives' guarantee actually hold? Querying might_contain() for all 1,000 inserted items gave 0 false negatives — every single item that went in was correctly reported as present. That's not a lucky run; it's mathematically guaranteed by the structure, since inserting an item sets exactly the bits that its own later lookup checks.
Second check, the interesting one: querying might_contain() for 200,000 freshly generated random strings that were never inserted. Out of those 200,000 genuine strangers to the filter, 18,810 came back as 'possibly present' — real false positives, not simulated ones. A few actual examples the filter got wrong: 'vnezbz', 'fdmgopioys', 'femywiwza', 'mflrxqgm', 'vkdbtmxfw' — none were ever inserted, but by coincidence, all three bit positions each one hashes to happened to already be set to 1 by other, unrelated words.
That gives an observed false positive rate of 18,810 / 200,000 = 9.405%.
Theoretical vs. Observed False Positive Rate
The standard formula for the expected false positive rate of a Bloom filter, given m bits, n inserted items, and k hash functions, is (1 - e^(-kn/m))^k. Plugging in m=5,000, n=1,000, k=3: kn/m = 3,000/5,000 = 0.6, e^(-0.6) ≈ 0.5488, so (1 - 0.5488)^3 = 0.4512^3 ≈ 0.09185, or 9.185%.
The observed rate from the actual run, 9.405%, is close to that but not identical — and that gap is expected, not a bug. The formula describes the average behavior of a probabilistic structure across infinitely many random insertions and queries; any single run with a finite bit array and a finite sample of query strings will land near that average with some natural variance, the same way flipping a fair coin 200,000 times won't produce exactly 100,000 heads.
It's worth re-deriving this by hand rather than trusting a formula on faith, since a surprising number deserves a second, independent check. After n insertions of k hash functions each, the probability a specific bit is still 0 is approximately e^(-kn/m) ≈ 0.5488 — each of the kn hash operations has a 1/m chance of missing that specific bit, and (1 - 1/m)^(kn) converges to e^(-kn/m) for large m. So the probability a given bit is 1 is 1 - 0.5488 = 0.4512. A false positive on a new item requires all k of its bit positions to happen to already be 1, which is 0.4512^3 ≈ 0.09185 — the same number as the formula, derived independently. Both the code and the by-hand math agree with each other, and both land close to what was actually measured.
Tuning m and k: The Real Trade-off
Two knobs control the false-positive rate: m (bits, really bits-per-item once n is fixed) and k (hash functions). More bits per item always lowers the false-positive rate, because there's more room for the bits an item touches to land on positions nobody else has claimed — but more bits cost more memory, so this is a direct memory-versus-accuracy trade.
k is subtler. Too few hash functions and each item's 'signature' is short and easy to collide with by chance. Too many hash functions and every insertion sets a larger fraction of the array to 1, saturating it faster — so there's an optimal k for a given m/n ratio, not 'more is always better.' That optimum is k = (m/n) × ln(2), which is about 0.693 × (m/n).
Working backward from a target false-positive rate, the bits-per-element needed at the optimal k works out to roughly 1.44 × log2(1/target rate). For a 1% target false-positive rate: -ln(0.01) = 4.6052, divided by (ln 2)^2 = 0.4805, gives about 9.6 bits per element — under 10 bits per item for a 99% guarantee of catching every genuine miss, which is the whole reason Bloom filters get used at scale: that's often 10-50x smaller than storing full keys or hashes for the same item count.
Where Bloom Filters Show Up in Real Systems
- Databases and key-value stores like Cassandra and HBase keep a Bloom filter per on-disk data file. Before doing an actual disk read to check if a key exists in that file, they check the filter first — a 'definitely absent' result skips the disk read entirely, which matters enormously when a key might be spread across dozens of files.
- CDNs and web caches use them for 'one-hit-wonder' filtering: don't bother caching a URL the first time it's requested, only after it's been requested at least once before — a Bloom filter of previously-seen URLs answers that question without storing every URL ever requested.
- Browsers' malicious-site warnings have historically used Bloom-filter-style structures so a URL can be checked against a huge block list locally, with only a rare, harmless false positive triggering a slower server-side double-check, and zero chance of ever missing a genuinely listed site.
- Bitcoin's lightweight (SPV) wallets use Bloom filters to ask full nodes for transactions relevant to their wallet without revealing exactly which addresses they own — the false positives here are a deliberate privacy feature, not just a side effect.
In every one of these cases, the pattern is identical: a huge, expensive, authoritative source of truth sits behind a small, fast, probabilistic gatekeeper, whose only job is to cheaply rule out the 'definitely not' cases so the expensive path only runs when there's a real chance of a hit.