The formula said 1.0039%. Ten million queries said 1.0056%.

The whole pitch for a Bloom filter is a number. You give it n, the number of items you plan to insert, and p, the false positive rate you can live with, and it hands you a memory budget. The textbook formula for how often it will lie to you is:

p = (1 - e^(-kn/m))^k
 
  m = bits in the array
  n = items inserted
  k = hash functions per item

That is a falsifiable claim, which makes Bloom filters unusual among the things we teach. So before writing anything else I built one, inserted 500,000 keys, and queried it with ten million keys that were definitely not in it. Then I did that at seven different sizings.

n = 500,000 inserted,  10,000,000 disjoint queries per row
 
 p target  bits/elem   k     theory   observed               95% CI  ratio
   0.1000      4.793   3   0.100713   0.100818 [0.100631,0.101004]  1.001
   0.0500      6.235   4   0.050269   0.050374 [0.050238,0.050509]  1.002
   0.0200      8.142   6   0.020092   0.020158 [0.020071,0.020245]  1.003
   0.0100      9.585   7   0.010039   0.010056 [0.009994,0.010118]  1.002
   0.0050     11.028   8   0.005017   0.005048 [0.005004,0.005092]  1.006
   0.0010     14.378  10   0.001000   0.000993 [0.000974,0.001013]  0.993
   0.0001     19.170  13   0.000100   0.000100 [0.000093,0.000106]  0.994

Nothing off by more than 0.7%. The famous rule of thumb (about 9.6 bits per element buys you a 1% error rate) survives contact with a real machine, and 1.44 bits per element per factor of two in 1/p holds all the way down to one in ten thousand.

I ran a second check against somebody else's numbers. The RocksDB wiki states that a standard Bloom filter at 10 bits per key with k = 6 has a false positive rate of 0.84%. The formula gives 0.8436%. My run gave 0.8588%. Three independent estimates inside two hundredths of a percentage point.

So the headline claim is solid. Everything interesting is in the places where it stops being.

Why "no" is a proof and "yes" is only a guess

A bit array of m bits, all zero. To insert, hash the item k ways, take each hash modulo m, set those bits. To query, hash the same k ways and look. Any zero bit means the item was never inserted — a proof, not a guess, because insertion only ever sets bits. All ones means maybe, because other items could have set every one of them.

The asymmetry is the point. Put one in front of Postgres and a request for an id that was never issued returns 404 off two bit probes in process memory: no Redis round trip, no SELECT, no disk seek. A request for an id that does exist pays the filter's cost on top of the lookup it was going to do anyway, which is why the filter only earns its place where the misses outnumber the hits.

The alternative people reach for first is a plain hash set of every valid key. I measured that too, because "it uses a lot of RAM" is not a number. A Set of two million v4 UUID strings in Node 22 cost 955.5 MiB of heap, measured with --expose-gc around the insert loop — 501 bytes per 36-character string. Extrapolated to a billion keys, about 467 GiB. The Bloom filter for the same billion keys at 1% is 1.12 GiB. Four hundred to one, not the five to one you get by counting UUID bytes and forgetting what a JavaScript string costs to store.

The optimal-k curve is too flat to measure the way I first measured it

k = (m/n) ln 2 is the standard result. At 9.585 bits per element it gives 6.644, so you round to 7. I swept k from 1 to 16 at that sizing with two million queries per point, and the empirical minimum did land on 7 — but only just. Theory separates k = 6 from k = 7 by one percent (0.010143 against 0.010039), and over ten independent replicates 6 took the minimum in one of them. The curve is very flat near the bottom.

That flatness is the finding, and it is easy to mistake for something more interesting. Here is one run at 16 bits per element, where the formula says k = 11.09:

=== m/n = 16.0  (k* = (m/n) ln 2 = 11.090) ===
  k      theory    observed  obs/theory
  9    0.000505    0.000504       0.997
 10    0.000470    0.000469       0.999
 11    0.000459    0.000490       1.068
 12    0.000466    0.000494       1.060
 13    0.000488    0.000512       1.049
empirical minimum at k = 10  (fp = 0.000469)

Read that table on its own and you conclude the formula is off by one, and I did, and I was wrong. At a rate of 0.00047 over two million queries you expect about 940 hits, so one standard deviation is 3.3% of the value and the 6.8% excursion at k = 11 is two of them. What that table needed was not a cleverer explanation, it was more queries. Thirty replicates, independent key and query sets each time, six million queries per k per replicate, 180 million per column:

=== m/n = 16, 30 replicates, 6,000,000 queries per k ===
  k    theory   mean obs   obs/theory   sd across reps   reps won
  9  0.000505   0.000504       0.9988         0.000010          0
 10  0.000470   0.000470       0.9995         0.000007          2
 11  0.000459   0.000457       0.9969         0.000010         25
 12  0.000466   0.000465       0.9998         0.000009          3
 13  0.000488   0.000487       0.9986         0.000011          0

Every k from 9 to 13 lands within 0.4% of theory, and 11 — the analytic answer, rounded from 11.09 — takes the minimum in twenty-five replicates out of thirty. The formula was right the whole time and the single run was noise.

What the formula is not, at 16 bits per element, is resolvable by a casual measurement. The gap between k = 11 and k = 12 is 1.5% of a rate near one in two thousand; at two million queries the sampling error is twice that, so one sweep hands you whichever k the noise favoured that afternoon. Which is the useful finding in its own right: two hash functions either side of (m/n) ln 2 the false positive rate barely moves, so k is a knob you spend on CPU rather than on accuracy. Take what the formula gives you and stop tuning it.

There is one k mistake that does cost you, and it shows up in a lot of published implementations: computing k with Math.ceil instead of Math.round. At a 5% target, (m/n) ln 2 is 4.3219.

m/n = 6.2352   (m/n) ln 2 = 4.3219
k=3  theory=0.055708  observed=0.055817
k=4  theory=0.050269  observed=0.050478   <- round()
k=5  theory=0.051029  observed=0.051226   <- ceil()
k=6  theory=0.055697  observed=0.055796

Ceiling costs you 25% more hashing and a slightly worse false positive rate. Round.

Two hashes, not seven — and the trap underneath

Computing seven independent hashes per lookup is wasteful, and you do not have to. Kirsch and Mitzenmacher showed that g_i(x) = h1(x) + i * h2(x) mod m gives you k usable indices from two hashes "without any increase in the asymptotic false positive probability" (Less Hashing, Same Performance: Building a Better Bloom Filter, Random Structures & Algorithms 33(2), 2008). Nearly every real implementation does this. I checked whether it actually holds at a size you would ship, and threw in some deliberately bad hashing for contrast:

m/n = 9.5851  k = 7  n = 200,000  queries = 2,000,000   theory = 0.010039
 
scheme                                          observed FP  obs/theory  chi2/dof
k independent murmur3 (seeds 0..6)                 0.009926       0.989      0.95
KM double hash, murmur3 seeds 0/42                 0.010113       1.007      0.98
KM double hash, murmur3 x64_128 halves             0.010016       0.998      0.99
KM double hash, FNV-1a / murmur3                   0.009952       0.991      0.93
k independent Java-style hashCode(i + s)           0.005058       0.504    311.44

Two hashes cost nothing measurable. The last row is the interesting one. That weak hash scored a better false positive rate than theory, and it is still broken: the chi-square statistic over its index distribution is 311 where a uniform hash gives about 1. 31 * h + c has no avalanche, so my structured keys ("key-N") and my structured queries ("miss-N") landed in different regions of the array and stopped colliding by accident. Change the key format and that 0.5% becomes something much worse. A false positive rate that beats the formula is not good news; it means your test data is correlated with your hash, and production data will not be.

// murmur3 returns an unsigned 32-bit value. One `|` and it isn't one any more.
const trapHash = 3463140808;          // murmur3_32('key-0', 0x9747b28c)
const trapM = 1917012;                // optimalBits(200_000, 0.01)
const trapIndex = (trapHash | 1) % trapM;   // -1760291
const trapBits = new Uint8Array(Math.ceil(trapM / 8));
 
trapBits[trapIndex >>> 3] |= 1 << (trapIndex & 7);          // "write"
trapBits[trapIndex >>> 3] & (1 << (trapIndex & 7));         // 0 — the write went nowhere
trapIndex >>> 3;                                            // 536650875, vs length 239627
((trapHash | 1) >>> 0) % trapM;                             // 1017137 — the fix

I found this by accident, testing a "force h2 odd" variant that appeared to improve the false positive rate eightfold. It had improved nothing. It had produced 83,297 false negatives out of 200,000 inserted keys, and because out-of-bounds reads on a Uint8Array are silent, the filter cheerfully reported a lower error rate while losing 41% of its contents. Assert that no false negative exists before you believe any false positive number.

The implementation

Self-contained, no dependencies. The murmur3 below matches Python's mmh3 exactly on eight test vectors at two seeds, which is how I know it is a real murmur3 and not a plausible-looking one.

function murmur3_32(key, seed = 0) {
  const data = new TextEncoder().encode(key);
  const c1 = 0xcc9e2d51, c2 = 0x1b873593;
  let h1 = seed >>> 0;
  const nblocks = data.length >>> 2;
  const view = new DataView(data.buffer, data.byteOffset, data.byteLength);
  for (let i = 0; i < nblocks; i++) {
    let k1 = view.getUint32(i * 4, true);
    k1 = Math.imul(k1, c1); k1 = (k1 << 15) | (k1 >>> 17); k1 = Math.imul(k1, c2);
    h1 ^= k1; h1 = (h1 << 13) | (h1 >>> 19); h1 = (Math.imul(h1, 5) + 0xe6546b64) | 0;
  }
  let k1 = 0;
  const tail = nblocks * 4;
  switch (data.length & 3) {
    case 3: k1 ^= data[tail + 2] << 16;
    case 2: k1 ^= data[tail + 1] << 8;
    case 1: k1 ^= data[tail];
            k1 = Math.imul(k1, c1); k1 = (k1 << 15) | (k1 >>> 17);
            k1 = Math.imul(k1, c2); h1 ^= k1;
  }
  h1 ^= data.length;
  h1 ^= h1 >>> 16; h1 = Math.imul(h1, 0x85ebca6b);
  h1 ^= h1 >>> 13; h1 = Math.imul(h1, 0xc2b2ae35);
  h1 ^= h1 >>> 16;
  return h1 >>> 0;                      // unsigned, and it stays that way
}
 
export function optimalBits(n, p) {
  return Math.ceil(-(n * Math.log(p)) / (Math.LN2 ** 2));
}
export function optimalHashes(m, n) {
  return Math.max(1, Math.round((m / n) * Math.LN2));   // round, not ceil
}
 
export class BloomFilter {
  constructor(expectedItems, falsePositiveRate) {
    this.m = optimalBits(expectedItems, falsePositiveRate);
    this.k = optimalHashes(this.m, expectedItems);
    this.bytes = new Uint8Array(Math.ceil(this.m / 8));
  }
  #indices(item) {
    const h1 = murmur3_32(item, 0);
    const h2 = murmur3_32(item, 0x9747b28c);
    const out = new Array(this.k);
    // both operands unsigned, so h1 + i*h2 stays well inside Number.MAX_SAFE_INTEGER
    for (let i = 0; i < this.k; i++) out[i] = (h1 + i * h2) % this.m;
    return out;
  }
  add(item) {
    for (const bit of this.#indices(item)) this.bytes[bit >>> 3] |= 1 << (bit & 7);
    return this;
  }
  mightContain(item) {
    for (const bit of this.#indices(item)) {
      if ((this.bytes[bit >>> 3] & (1 << (bit & 7))) === 0) return false;
    }
    return true;
  }
  predictedFalsePositiveRate(n) { return (1 - Math.exp(-this.k * n / this.m)) ** this.k; }
}

The tests that produced the top table. The order matters more than the assertions do: false negatives first, then bounds, then the rate. Check them in the other order and a broken filter reports a beautiful false positive rate for a set it has half-lost.

const assert = (cond, msg) => { if (!cond) throw new Error('FAILED: ' + msg); };
 
assert(murmur3_32('abc', 0) === 3017643002, 'murmur3 vector, seed 0');
assert(murmur3_32('abc', 42) === 1313807976, 'murmur3 vector, seed 42');
assert(optimalBits(100_000_000, 0.01) === 958505838, 'm for n=1e8 at p=1%');
assert(optimalHashes(958505838, 100_000_000) === 7, 'k for 9.585 bits per element');
 
const N = 200_000, QUERIES = 2_000_000;
const filter = new BloomFilter(N, 0.01);
for (let i = 0; i < N; i++) filter.add('key-' + i);
 
// 1. the one guarantee. check this before you believe anything else.
let missing = 0;
for (let i = 0; i < N; i++) if (!filter.mightContain('key-' + i)) missing++;
assert(missing === 0, `${missing} false negatives — the filter is broken`);
 
// 2. every index inside the array (catches the signed-int trap)
let outOfRange = 0;
for (let i = 0; i < 50_000; i++) {
  const a = murmur3_32('probe-' + i, 0), b = murmur3_32('probe-' + i, 0x9747b28c);
  for (let j = 0; j < filter.k; j++) {
    const bit = (a + j * b) % filter.m;
    if (!Number.isInteger(bit) || bit < 0 || bit >= filter.m) outOfRange++;
  }
}
assert(outOfRange === 0, `${outOfRange} indices outside [0, m)`);
 
// 3. measured rate has to track the formula
let hits = 0;
for (let i = 0; i < QUERIES; i++) if (filter.mightContain('miss-' + i)) hits++;
const observed = hits / QUERIES, predicted = filter.predictedFalsePositiveRate(N);
assert(observed / predicted > 0.9 && observed / predicted < 1.1,
       `observed/predicted = ${(observed / predicted).toFixed(3)}, outside ±10%`);
console.log(`predicted ${(predicted * 100).toFixed(4)}%  observed ${(observed * 100).toFixed(4)}%`);

Output on Node 22: predicted 1.0039% observed 1.0181%. Runs in under four seconds.

The Python version, using mmh3 for the 128-bit hash and slicing it in half rather than hashing twice:

import math
import mmh3
from bitarray import bitarray
 
class BloomFilter:
    def __init__(self, expected_items: int, fp_rate: float):
        self.m = math.ceil(-(expected_items * math.log(fp_rate)) / (math.log(2) ** 2))
        self.k = max(1, round((self.m / expected_items) * math.log(2)))
        self.bits = bitarray(self.m)
        self.bits.setall(0)
 
    def _indices(self, item: str):
        h1, h2 = mmh3.hash64(item, seed=0, signed=False)
        return [(h1 + i * h2) % self.m for i in range(self.k)]
 
    def add(self, item: str) -> None:
        for bit in self._indices(item):
            self.bits[bit] = 1
 
    def might_contain(self, item: str) -> bool:
        return all(self.bits[bit] for bit in self._indices(item))

Same harness, same sizing: predicted 1.0039% observed 1.0003% ratio 0.996. Note signed=False — mmh3.hash returns a signed integer by default. Python's modulo happens to rescue you; JavaScript's does not.

Deletion, and why the usual fix has a hole in it

You cannot remove an item from a standard Bloom filter. Bits are shared, so clearing them corrupts every other item that touched them — manufacturing the one failure mode the structure is supposed to rule out.

The standard answer is a counting Bloom filter: replace each bit with a small counter, increment on insert, decrement on delete. Four bits per counter is the usual choice, and the usual claim is that four bits is plenty. On clean traffic it is — I inserted 200,000 distinct items at 9.585 bits per element with k = 7 and the highest counter reached 8, nowhere near the ceiling of 15.

Then I inserted the same item more than once, which is what a retry storm does to an endpoint that does not deduplicate:

=== 4-bit counting Bloom filter, m/n = 9.585, k = 7, n = 200,000 ===
each item inserted once                  max counter =  8   counters > 15: 0
same item re-inserted 3x                 max counter = 24   counters > 15: 220
same item re-inserted 6x                 max counter = 48   counters > 15: 72492

And here is what a saturated counter costs. One hot key gets inserted 40 times, saturating its seven counters at 15. Then the retries get rolled back (41 decrements) and the counters walk down to zero, taking other people's items with them:

counters for 'key-0' after 40 inserts: [15, 15, 15, 15, 15, 15, 15]
after rolling back 41 inserts:         [0, 0, 0, 0, 0, 0, 0]
FALSE NEGATIVES among 50,000 live keys: 3

Three keys that are in the set now report absent. Fan et al. name this in their cuckoo filter paper: "Inserting the same item kb + 1 times will cause the insertion to fail. This is similar to counting Bloom filters where duplicate insertion causes counter overflow." A counting filter needs deduplication upstream, or wider counters, or it will quietly lie in the direction you cannot tolerate.

The other failure is sizing. You have to know n in advance, and the penalty for guessing low is not gradual:

designed for n = 200,000 at p = 1%:  m = 1,917,012 bits, k = 7
  actual n   n/design    fill    theory  observed
    200000       1.0x  0.5185   0.01004   0.01021
    400000       2.0x  0.7677   0.15745   0.15713
   1000000       5.0x  0.9740   0.83188   0.83222
   2000000      10.0x  0.9993   0.99530   0.99541

Twice your design capacity and you are at 15.7% — a sixteenfold blowout from one doubling. By 10x the filter says "probably yes" to everything and has become a fixed-cost way of doing nothing. Rebuild on a schedule, or use something that scales: Redis's Bloom filter chains sub-filters as it fills (its BF.ADD docs give the complexity as "O(k), where k is the number of hash functions used by the last sub-filter"), and Akamai's implementation rotates a primary and secondary filter rather than letting one saturate.

The cost model is the part most articles get wrong

The claim you see repeated is that a lookup costs k random memory accesses — seven cache misses at a 1% target. True for a positive lookup. Not true for the negative lookups that are the entire reason you deployed the thing, because you stop at the first zero bit and the array is only half full. I counted probes:

   m/n   k   fill  mean probes/neg   predicted by fill
 9.585   7 0.5184            2.056               2.056
14.378  10 0.5012            2.002               2.003
20.000  14 0.5034            2.016               2.014

Two, not seven. Fan et al. state the same thing from the analysis side: "A negative query to a space optimized Bloom filter reads two bits on average before it returns, because half of the bits are set."

The cache concern is real, though, and there is one honest public account of it. Cloudflare's Marek Majkowski built a Bloom filter to deduplicate a billion lines of IP data in 2020, profiled it, found 87.2% of cycles inside the hot loop and 26.9% of them on the single mov that dereferences the bit array, and abandoned it for a hash table with linear probing — 12 seconds down to 2.1. His conclusion: "Bloom filters are great, as long as they fit into the L3 cache. The moment this assumption is broken, they are terrible." Cloudflare's documented experience is taking one out, not running them at the edge.

RocksDB solved the same problem differently. Its "full filter" format constrains all of a key's probe bits to a single CPU cache line, which the wiki says "limits the CPU cache misses to one per key (per filter)" — its own math puts that at 0.95% cache-local versus 0.84% unblocked at the same sizing. Since 6.15.0 it also ships Ribbon filters, saving about 30% of the space for 3-4x the construction CPU: NewRibbonFilterPolicy(9.9) hits the same 1% at roughly 7 bits per key instead of 9.6.

Cassandra, Postgres, Akamai, and one myth

Cassandra keeps a Bloom filter per SSTable, off-heap, and exposes the target rate as bloom_filter_fp_chance. The default is 0.1 for tables using LeveledCompactionStrategy and 0.01 for everything else, and the docs note that dropping from 0.1 to 0.01 costs "about three times as much memory". Changing it takes effect only when the SSTables are rewritten, because the filter is computed at write time and stored as the Filter component of the file. RocksDB embeds a filter in every SST file and loads it when the file is opened.

Postgres has Bloom filters, but not where people usually claim. bloom is a contrib index access method — install the extension, create an index that stores a lossy signature per row, 80 bits by default. It is for tables with many columns queried in arbitrary combinations, where one bloom index replaces a pile of btree indexes. The documentation's own example builds a 153 MB bloom index against 386 MB for the equivalent composite btree, and every match still gets rechecked against the heap. It is not part of the normal index path and it does not sit in front of B-trees.

Akamai uses a Bloom filter for a cache-on-second-hit rule: over three quarters of objects requested from a CDN edge are "one-hit wonders", so the filter records what has been seen and only the second request earns a place on disk. Maggs and Sitaraman published the production numbers (Algorithmic Nuggets in Content Delivery, ACM SIGCOMM CCR, 2015) — byte hit rate rose from 74% to 83%, disk writes fell from 10,209/s to 5,738/s, and average disk read latency dropped from 15.6 ms to 11.9 ms across a 47-server cluster.

Cuckoo filters, honestly

Fan, Andersen, Kaminsky and Mitzenmacher's Cuckoo Filter: Practically Better Than Bloom (CoNEXT 2014) is the paper, and the tradeoff is narrower than the title suggests. Cuckoo filters store short fingerprints in buckets rather than bits in an array. They support deletion, any query reads a fixed number of buckets giving "(at most) two cache line misses", and the space claim is specific: cuckoo filters with semi-sorting "are more space efficient than Bloom filters when ε < 3%", crossing over at 7.2 bits per item.

The costs are real too. Insertion can fail — the paper's algorithm gives up after MaxNumKicks relocations and returns Failure, at which point you resize. Deletion is only safe for items you actually inserted: "deleting a non-inserted item might unintentionally remove a real, different item that happens to share the same fingerprint." And the duplicate-insertion ceiling is the same one counting Bloom filters have.

A Bloom filter has none of those cliffs. It degrades continuously, it cannot fail an insert, and a correct one fits in fifty lines. That is worth something.

Where the two agree, and where they don't

The sizing formula is the most trustworthy thing in this article. Seven configurations, ten million queries each, never off by more than seven parts in a thousand, and within two hundredths of a percentage point of RocksDB's independently published figure. If you need 1% at a hundred million keys, budget 958,505,838 bits, or 114 MB, and expect to get 1%.

Everything downstream of that number is where prediction and measurement come apart, and they come apart in a consistent direction: the model is right about the false positive rate and silent about the cost. It implies k memory probes when negative lookups take two. It says nothing about a filter that does not fit in L3 losing to a hash table by 6x, or four-bit counters surviving one clean pass and dying on a retry storm, or JavaScript turning a bit index negative and answering your queries out of an array it does not own.

None of that makes the formula wrong. It makes it a statement about one variable in a system that has several. Size the array with it, then go and measure what it is silent about: probes per negative lookup, resident set size, what happens at twice the design load.

A formula this good at the one thing it promises is the most dangerous kind, because it buys credit for the four things it never mentioned.