Is a Bloom filter's 1% false positive rate really 1%?

Yes. At one million inserted keys a filter designed for 1% returned 0.010108 — 20,217 false positives out of 2,000,000 probes against a predicted 0.010039, an error of 0.7%. Across nine configurations spanning three target rates and three corpus sizes, the worst disagreement between formula and measurement was 4.7%, and that one had only 1,906 false positives in it, so most of the gap is counting noise. The formula is not where Bloom filters go wrong.

What does go wrong is everything around it. The same filter, filled to twice its design capacity, returned 15.7%. Swapping the hash for a sum of character codes returned 99.9%. Clearing the bits of one key to "delete" it broke seven other keys.

Hardware: Apple M3, 16 GB, macOS 26.4.1, Node v23.5.0. No dependencies, no network. Keys are 36-character UUID-shaped strings generated deterministically from an index; the present set (indices 0..n) and the probe set (indices 50,000,000..52,000,000) are disjoint by construction, and I checked — overlap zero. Nothing here needs more than about 400 MB of heap.

The short answer

• The formula holds. Measured false positive rates matched (1 - e^(-kn/m))^k to within 1.5% at every configuration with more than 10,000 false positives in the sample. At n = 1,000,000 and a 0.1% target the measurement was 0.001001 against a predicted 0.001000.
• A Bloom filter has no false negatives, and this is not a claim — it is a count. 3,330,000 lookups of keys that had been inserted returned present 3,330,000 times. Zero misses, at every size and every target rate.
• Overfilling is the failure nobody instruments. A filter sized for 100,000 keys at 1% gives 5.7% at 150,000 keys, 15.7% at 200,000 and 83.3% at 500,000. It never throws, never logs, and never stops answering.
• Hash quality is not a detail. With a sum-of-character-codes hash the measured rate was 0.99923 — the filter said "maybe" to essentially everything, while only 0.64% of its bits were set. Truncating a good hash to 16 bits gave 38.5%.
• A Set is faster than the Bloom filter at every size I measured, up to and including one million keys (148 ns vs 192 ns per lookup). The Bloom filter's entire case is memory: 1.198 bytes per key against 85 bytes for the Set, a 71x saving. There is no speed crossover below a million keys, so pick on memory alone.

How the filter is built

One construction, stated exactly so the numbers mean something. The bit array is a Uint8Array of ceil(m/8) bytes; the k indices come from Kirsch-Mitzenmacher double hashing over MurmurHash3 x86_32:

const h1 = murmur3(key, 0);
const h2 = murmur3(key, h1) | 1;          // odd, so it is coprime with 2^32
for (let i = 0; i < k; i++) {
  const idx = ((h1 + Math.imul(i, h2)) >>> 0) % m;
  bits[idx >>> 3] |= 1 << (idx & 7);
}

m and k come from the textbook sizing, m = ceil(-n ln p / (ln 2)^2) and k = round((m/n) ln 2). For 1% that is 9.585 bits and 7 probes per key; for 0.1%, 14.378 bits and 10 probes.

The second hash is seeded with the first — cheaper than a 64-bit hash split into halves. Kirsch-Mitzenmacher says double hashing costs you nothing asymptotically; the next table is what "nothing" looks like on real keys.

Does the formula hold?

Two million probes against known-absent keys, at each of nine configurations.

Every row is within 5%, and the six rows with a five-figure false positive count are within 1.5%. The 0.1% rows wobble more because 2,000 events is a small sample — expected standard error about 2.2%, and that is the spread observed.

This is a boring result, and worth stating plainly, because the interesting version of this article — "the formula lies to you" — is not true. If your Bloom filter is missing its target, the formula is not the reason.

The false negative column is the other half. A key that was inserted sets k bits and nothing ever unsets them, so a false answer is always correct. That is a proof, not a measurement — but proofs do not catch implementation bugs, and this one does. All 3,330,000 present-key lookups returned present.

What happens when you overfill it?

You size a filter for the items you have. Then the item count grows, and nothing in the data structure notices. A filter designed for n = 100,000 at p = 0.01 — 958,506 bits, k = 7 — pushed past its capacity:

The degradation is not linear and it is not gentle. Doubling the load does not double the false positive rate, it multiplies it by 16. At 5x the filter agrees with 83% of the queries you send it, which for most uses means it has stopped being an index and become a return true.

The formula tracks it the whole way down, which is the useful part: keep a counter of insertions beside the filter and expose (1 - e^(-kn/m))^k as a metric. Three floating-point operations, and the only warning you will get.

Overfilling never produces a false negative — 385,718 present-key checks across those rows, zero misses. A rotting Bloom filter degrades into uselessness without ever becoming wrong in the direction that would page you.

How much does a bad hash cost?

The formula assumes the k indices are independent and uniform over m. Two ways to break that, both measured at n = 100,000 with one million probes:

The additive checksum is the instructive one. A 36-character key made of hex digits and dashes has a character-code sum confined to a range of a few thousand, so every index lands in a sliver of the bit array. Only 0.64% of the bits were ever set, and the filter still answered "maybe" to 99.9% of queries — the bits it did set were the only bits anyone ever looked at. A filter that is almost entirely zeros can still be useless.

The truncation case is subtler and more likely to be your bug. The hash is genuinely good; it just does not produce enough distinct values. With 65,536 possible digests over a 958,506-bit array, the pigeonhole does the rest.

The bit-set percentage is the cheap diagnostic. A correctly sized, correctly hashed filter at its design capacity sits at almost exactly 50% — that is what optimal k means. At 0.6% or 30%, the hash is the suspect.

Is k = (m/n) ln 2 actually optimal?

Sweeping k from 1 to 16 at fixed m = 958,506 and n = 100,000, where the formula predicts k = 6.644:

k = 7 wins, exactly as round(6.644) promises. But look at how flat the floor is: k = 5 gives 0.011126 against k = 7's 0.009848 — 13% worse — while querying 8% faster and touching two fewer cache lines per lookup. If lookups are your bottleneck, rounding k down is nearly free. Rounding it up is not: k = 16 costs 3.6x the false positives and 41% more time for nothing at all.

When is a plain Set better?

Here is where I expected a crossover and did not find one. Memory at p = 0.01 with 36-character UUID keys, measured with --expose-gc and process.memoryUsage().heapUsed around each structure:

The Bloom filter is smaller at every size, including a thousand keys. There is no n below which the Set wins on bytes, because the Set pays ~64 bytes for each 36-character string plus ~21-32 bytes of hash table entry, and the filter pays 9.585 bits regardless.

(A caveat worth 60 seconds: my first attempt measured 381-425 bytes per key, because the keys were built by concatenating slices and V8 was retaining the parent strings behind ConsString and SlicedString wrappers. Building the same characters into an array and calling join('') cut it to 85. If a Set's footprint looks absurd, suspect the strings, not the Set.)

Speed, best of five runs after a warmup, one million probes of absent keys:

The Set is faster everywhere, but the trend lines differ. The Bloom filter's lookup is flat — 215 ns down to 192 ns as n grows 1000x — because it is always k = 7 random reads into a small array. The Set goes from 20 ns to 148 ns as its 85 MB of strings falls out of cache. They cross around two to three million keys.

So the honest rule is a budget question, not a size threshold. At n = 10,000 you are trading 1% wrong answers for 987 KB, which is almost never worth it. The filter earns its place when 85 bytes per key is a number you cannot pay: a cache in a 128 MB container, a filter shipped to a browser, one filter per tenant across thousands of tenants, or a set in front of a network call where a false positive is a wasted round trip rather than a wrong answer. The same reasoning runs through near-duplicate document detection, where a 512-byte MinHash signature replaces the document, and perceptual image hashing, where 8 bytes replace the image. A probabilistic structure is a compression decision first.

What does one delete cost?

A standard Bloom filter cannot delete. The usual explanation is that clearing a key's bits may clear bits another key relies on. Here is that in numbers, in the same n = 100,000, k = 7 filter:

One delete out of a hundred thousand keys destroys seven others: at k = 7 with the array half full, nearly every bit you clear is load-bearing for somebody. Worse than the count suggests, too — the structure's one guarantee is that false means definitely absent, and after a single delete that guarantee is gone. Deleting 10% of the keys made 40% of the survivors vanish.

A 4-bit counting Bloom filter over the same geometry fixes it. Same m, same k, counters instead of bits, 479,253 bytes — exactly 4x the plain filter. After deleting the same 10,000 keys: zero false negatives, and 65 of the deleted keys still reported present, which is the residual 0.65% false positive rate doing its normal job. The post-deletion rate on absent keys was 0.005879 against a predicted 0.006021 for a filter holding 90,000 keys. No counter saturated at 15 here; with skewed insertion one would, and a saturated counter can never be decremented again without reintroducing false negatives.

I did not implement a cuckoo filter, so I will not put a number on it. The published trade is that it supports deletion and is more compact than a counting Bloom filter below roughly 3% false positive rate, at the cost of insertions that can fail once the table is full — which turns "the filter silently rots" into "the filter refuses writes", a failure mode you can alert on.

Check it yourself

One file, no dependencies, Node 18 or newer. It reproduces the headline table, the overfill degradation, the cost of one delete and the weak-hash collapse.

node bloom-check.mjs 100000       # ~15 s
node bloom-check.mjs 1000000      # ~90 s

Output on this machine at n = 100,000:

node v23.5.0  n=100000  probes=1000000

target      m        k   theory     measured   false negatives
0.05        623523   4  0.050269   0.050580   0
0.01        958506   7  0.010039   0.009848   0
0.001      1437759  10  0.001000   0.000965   0

overfilling a filter designed for n at p=0.01:
load   inserted   theory     measured
1x       100000   0.010039   0.009848
2x       200000   0.157453   0.156899
5x       500000   0.831885   0.832850

what one "delete" costs (clearing the k bits of a single key):
deleted 1 key of 100000; other keys now reported ABSENT: 7

weak hash (sum of character codes) at p=0.01:
theory 0.010039   measured 0.999230

Here is the whole file. The Bloom class is the entire implementation — optimal(n, p) for sizing, add, has, and an unsafeDelete that exists only so the damage can be counted.

// bloom-check.mjs — node bloom-check.mjs   (Node 18+, no dependencies)
function murmur3(str, seed = 0) {
  let h1 = seed | 0; const len = str.length, nb = len >> 2;
  for (let i = 0; i < nb; i++) {
    const j = i << 2;
    let k1 = (str.charCodeAt(j) & 255) | ((str.charCodeAt(j+1) & 255) << 8) |
             ((str.charCodeAt(j+2) & 255) << 16) | ((str.charCodeAt(j+3) & 255) << 24);
    k1 = Math.imul(k1, 0xcc9e2d51); k1 = (k1 << 15) | (k1 >>> 17);
    k1 = Math.imul(k1, 0x1b873593); h1 ^= k1;
    h1 = (h1 << 13) | (h1 >>> 19); h1 = (Math.imul(h1, 5) + 0xe6546b64) | 0;
  }
  let k1 = 0; const t = nb << 2;
  switch (len & 3) {
    case 3: k1 ^= (str.charCodeAt(t+2) & 255) << 16;
    case 2: k1 ^= (str.charCodeAt(t+1) & 255) << 8;
    case 1: k1 ^= str.charCodeAt(t) & 255;
      k1 = Math.imul(k1, 0xcc9e2d51); k1 = (k1 << 15) | (k1 >>> 17);
      k1 = Math.imul(k1, 0x1b873593); h1 ^= k1;
  }
  h1 ^= len; h1 ^= h1 >>> 16; h1 = Math.imul(h1, 0x85ebca6b);
  h1 ^= h1 >>> 13; h1 = Math.imul(h1, 0xc2b2ae35); h1 ^= h1 >>> 16;
  return h1 >>> 0;
}
class Bloom {
  constructor(m, k, hash = murmur3) { this.m = m; this.k = k; this.hash = hash; this.bits = new Uint8Array(Math.ceil(m/8)); }
  static optimal(n, p, hash = murmur3) {
    const m = Math.ceil((-n * Math.log(p)) / (Math.LN2 ** 2));
    return new Bloom(m, Math.max(1, Math.round((m/n) * Math.LN2)), hash);
  }
  _each(key, f) {                        // Kirsch-Mitzenmacher double hashing
    const h1 = this.hash(key, 0), h2 = this.hash(key, h1) | 1;
    for (let i = 0; i < this.k; i++) if (f(((h1 + Math.imul(i, h2)) >>> 0) % this.m) === false) return false;
    return true;
  }
  add(key) { this._each(key, (i) => { this.bits[i >>> 3] |= 1 << (i & 7); }); }
  has(key) { return this._each(key, (i) => (this.bits[i >>> 3] & (1 << (i & 7))) !== 0); }
  unsafeDelete(key) { this._each(key, (i) => { this.bits[i >>> 3] &= ~(1 << (i & 7)); }); }
}
const HEX = '0123456789abcdef';
const keyAt = (i) => {                   // deterministic 36-char UUID-shaped key
  const w = [murmur3(String(i),0), murmur3(String(i)+':b',1), murmur3(String(i)+':c',2), murmur3(String(i)+':d',3)];
  const o = new Array(36); let p = 0;
  for (const x of w) for (let j = 7; j >= 0; j--) {
    if (p===8||p===13||p===18||p===23) o[p++]='-';
    o[p++] = HEX[(x >>> (j*4)) & 15];
  }
  return o.join('');
};
const theory = (m, k, n) => (1 - Math.exp(-k * n / m)) ** k;

const N = Number(process.argv[2] || 100000), PROBES = 1_000_000;
const absent = Array.from({length: PROBES}, (_, i) => keyAt(50_000_000 + i));
console.log(`node ${process.version}  n=${N}  probes=${PROBES}\n`);
console.log('target      m        k   theory     measured   false negatives');
for (const p of [0.05, 0.01, 0.001]) {
  const f = Bloom.optimal(N, p);
  for (let i = 0; i < N; i++) f.add(keyAt(i));
  let fn = 0; for (let i = 0; i < N; i++) if (!f.has(keyAt(i))) fn++;
  let fp = 0; for (let i = 0; i < PROBES; i++) if (f.has(absent[i])) fp++;
  console.log(`${String(p).padEnd(8)} ${String(f.m).padStart(9)} ${String(f.k).padStart(3)}  ${theory(f.m,f.k,N).toFixed(6)}   ${(fp/PROBES).toFixed(6)}   ${fn}`);
}
console.log('\noverfilling a filter designed for n at p=0.01:');
console.log('load   inserted   theory     measured');
{
  const f = Bloom.optimal(N, 0.01); let ins = 0;
  for (const mult of [1, 2, 5]) {
    for (const stop = Math.round(N*mult); ins < stop; ins++) f.add(keyAt(ins));
    let fp = 0; for (let i = 0; i < PROBES; i++) if (f.has(absent[i])) fp++;
    console.log(`${(mult+'x').padEnd(6)} ${String(ins).padStart(8)}   ${theory(f.m,f.k,ins).toFixed(6)}   ${(fp/PROBES).toFixed(6)}`);
  }
}
console.log('\nwhat one "delete" costs (clearing the k bits of a single key):');
{
  const f = Bloom.optimal(N, 0.01);
  for (let i = 0; i < N; i++) f.add(keyAt(i));
  f.unsafeDelete(keyAt(0));
  let broken = 0; for (let i = 1; i < N; i++) if (!f.has(keyAt(i))) broken++;
  console.log(`deleted 1 key of ${N}; other keys now reported ABSENT: ${broken}`);
}
console.log('\nweak hash (sum of character codes) at p=0.01:');
{
  const weak = (s, seed=0) => { let h = seed>>>0; for (let i=0;i<s.length;i++) h = (h + s.charCodeAt(i))>>>0; return h; };
  const f = Bloom.optimal(N, 0.01, weak);
  for (let i = 0; i < N; i++) f.add(keyAt(i));
  let fp = 0; for (let i = 0; i < PROBES; i++) if (f.has(absent[i])) fp++;
  console.log(`theory 0.010039   measured ${(fp/PROBES).toFixed(6)}`);
}

Same discipline applied to throughput rather than accuracy: how fast a Postgres queue actually is.