· 6 min read
Bloom filters: how they work and how to size them
Bloom filters answer "definitely not" or "maybe" in a few bits per key. Learn how they work, how to size one, and where they skip slow lookups.

A Bloom filter is a small, fixed-size bit array that answers one question very cheaply: "have I possibly seen this key before?" It can say "definitely not" or "maybe", never a false "no". That makes it a fast gate in front of expensive lookups: if the filter says a key is absent, you skip the disk read, the network call or the database query entirely.
The price is a tunable false positive rate. You pick how wrong "maybe" is allowed to be, and the math tells you how much memory that costs.
What is a Bloom filter?
A Bloom filter is an array of m bits, all starting at zero, plus k hash functions. A hash function here is anything that maps a key to a number that looks random but is always the same for the same key.
To add a key, you hash it k times, map each result to a position in the array, and set those k bits to 1. To check a key, you hash it the same way and look at the same k positions:
- If any of those bits is 0, the key was never added. That answer is exact.
- If all of them are 1, the key was probably added. Those bits might also have been set by other keys, which is where false positives come from.
The filter doesn't store keys at all. It stores a smeared fingerprint of every key at once, which is why it is so small and why you can't list what's inside it.
How does a Bloom filter avoid expensive lookups?
The pattern is always the same: put the filter in memory, in front of something slow, and only pay for the slow path when the filter says "maybe".
Some places where this shows up:
- LSM-tree storage engines. An LSM tree writes data into many immutable sorted files and merges them over time. RocksDB, Cassandra and similar engines keep a Bloom filter per file, so a read for a missing key can skip most files without touching disk. Cassandra exposes this per table as
bloom_filter_fp_chance. - Cache penetration. Requests for keys that don't exist miss the cache every time and fall through to the database. A filter of all valid keys lets you reject those requests before they reach either. It is a different problem from the expired-hot-key case in cache stampede, but it hurts the database the same way.
- "Seen before" checks. Crawlers skipping URLs they already fetched, feeds hiding items a user already saw, signup forms checking if a username is likely taken before a real query.
In every case a false positive costs you one wasted lookup, and a true negative saves one. As long as most queried keys are absent, the filter pays for itself.
How do you size a Bloom filter?
You need two inputs: n, the number of keys you expect to insert, and p, the false positive rate you can tolerate. The optimal sizes are:
m = -n × ln(p) / (ln 2)² bits in the array
k = (m / n) × ln 2 number of hash functions
The useful shortcut is bits per key, which depends only on p:
| Target false positive rate | Bits per key | Hash functions | Memory for 1M keys |
|---|---|---|---|
| 10% | 4.8 | 3 | ~0.6 MiB |
| 1% | 9.6 | 7 | ~1.1 MiB |
| 0.1% | 14.4 | 10 | ~1.7 MiB |
| 0.01% | 19.2 | 13 | ~2.3 MiB |
Each extra 4.8 bits per key cuts the false positive rate by ten. That's why "about 10 bits per key for 1%" is the number most people remember. Compare it with storing the keys themselves: a million 36-character UUIDs is over 34 MB before any hash table overhead.
Here is a minimal implementation that uses double hashing, a common trick that derives all k positions from two hash values instead of running k separate hash functions:
import hashlib, math
class Bloom:
def __init__(self, n, p):
self.m = math.ceil(-n * math.log(p) / math.log(2) ** 2)
self.k = max(1, round(self.m / n * math.log(2)))
self.bits = bytearray((self.m + 7) // 8)
def _positions(self, item):
h = hashlib.sha256(item.encode()).digest()
h1 = int.from_bytes(h[:8], "big")
h2 = int.from_bytes(h[8:16], "big") | 1
return [(h1 + i * h2) % self.m for i in range(self.k)]
def add(self, item):
for pos in self._positions(item):
self.bits[pos // 8] |= 1 << (pos % 8)
def might_contain(self, item):
return all(self.bits[pos // 8] & (1 << (pos % 8))
for pos in self._positions(item))
Sized for 100,000 keys at 1%, it uses 958,506 bits (about 117 KiB) and 7 hashes. After inserting those keys, all 100,000 lookups for them return true, and 100,000 lookups for keys that were never added return true about 1.02% of the time. That matches the target.
What happens when a Bloom filter fills up?
The sizing above assumes you know n. If you insert more keys than planned, more bits flip to 1 and the false positive rate climbs fast. Push three times the planned keys into the same filter and the false positive rate in that test jumps to about 43%. At that point the filter is skipping very little work.
There are a few ways to handle growth:
- Size for the peak, not today. Memory is cheap at 10 bits per key; underestimating
nis the expensive mistake. - Rebuild periodically. If keys come from a database table, rebuild the filter from the table on a schedule and swap it in atomically.
- Use a scalable filter. A scalable Bloom filter adds a new, larger layer when the current one reaches capacity, and checks all layers on lookup. Redis's
BF.RESERVEcommand creates one with an expansion factor, so it grows instead of degrading.
Watch the fill ratio, the fraction of bits set to 1. An optimally sized filter at capacity sits near 50%. Well above that means it's overfull.
Can you delete from a Bloom filter?
Not from a standard one. Clearing a key's bits could also clear bits another key depends on, which would create false negatives, the one error a Bloom filter promises never to make.
If you need deletes, the common options are:
| Structure | Deletes | Trade-off |
|---|---|---|
| Standard Bloom filter | No | Smallest and simplest |
| Counting Bloom filter | Yes | A small counter per slot instead of a bit, so several times the memory |
| Cuckoo filter | Yes | Stores short fingerprints; often similar size to Bloom at low error rates, but inserts can fail when it's nearly full |
For many systems the simplest answer is still a periodic rebuild. Deleted keys stay in the filter until then, which only means a few extra false positives.
Key takeaways
- A Bloom filter answers "definitely not" or "maybe" for a key, using a few bits per key and no stored keys.
- Put it in memory in front of a slow lookup; it saves work whenever most queried keys are absent.
- About 9.6 bits per key gives a 1% false positive rate, and each extra 4.8 bits cuts it tenfold.
- Overfilling ruins it quietly, so size for peak load, rebuild, or use a scalable variant.
- Standard filters can't delete; use a counting or cuckoo filter if you truly need it.
FAQ
Can a Bloom filter give a false negative?
No, as long as you never remove bits and use the same hash functions for adds and checks. If it says a key is absent, it was never added.
How many hash functions should a Bloom filter use?
Use k = (m / n) × ln 2, rounded. For a 1% false positive rate that's 7. In practice you compute them from two base hashes with double hashing.
Is a Bloom filter the same as a cache?
No. A cache stores values so you can skip a lookup for keys that exist. A Bloom filter stores nothing retrievable and lets you skip lookups for keys that don't.