Bloom filter sizing

The optimal hash count is (m/n) x ln2, which at 10 bits per element is 6.93, so 7. Below it the filter is under-probed and too many keys share a signature; above it every insert sets more bits and the array fills faster than the extra probe is worth. Both directions make the rate worse, which is why there is an optimum at all.

At 10 bits per element with 7 hashes, 47 of 5,000 absent keys returned a false positive, a rate of 0.94% against a predicted 0.82%.

Before reading anything into the gap, check the band: with 5,000 queries at this rate the formula expects 41 false positives give or take 6, so anything between 28 and 54 is the same answer. 47 is inside it, so measured and predicted agree here. Raise the query count to shrink the band.

The middle number also assumes the k probes set k distinct bits. They do not - a key can probe the same bit twice - so slightly fewer bits get set than it expects. The third number feeds the actual count of set bits back into the same exponent, so it is the closer of the two whenever the fill drifts from what the formula assumed. That is the assumption becoming visible, not an error.

Read the other way: a 0.94% rate needs about 9.7 bits per element, from m/n = -log2(eps) / ln2. That identity has no n in it, which is the surprising part - the bits per element you need depends only on the rate you will tolerate, never on how many keys you plan to store.

This is a sample, not the whole array - at 10 bits per element and 5,000 keys there are 50,000 of them. Drag the bits-per-element slider down and watch it saturate: once nearly every bit is set, every query finds all k of its probes already true and the filter starts answering "maybe" to everything, which is the failure mode of an undersized filter.

One probe found a 0, so the filter says definitely absent and stops. It cannot be wrong about this: an inserted key would have set that bit.

The error is one-sided, and this panel is where that stops being a slogan. A zero is a proof - no insert could have left it clear. A run of ones is only an absence of evidence. That asymmetry is the entire reason a filter like this is safe to put in front of a disk: a "no" skips the read, and a "maybe" costs you nothing but the read you were going to do anyway.

Every row here is a filter that was really built and really queried 5,000 times, not a formula evaluated at eight points - otherwise the table would only show the prediction agreeing with itself. Roughly 10 bits per element buys about 1%, and each further 4.8 bits divides the rate by ten - that second figure is the sizing identity again, since 1/ln2 x log2(10) is 4.8.

Real: the bit array is a real Uint8Array with real bit operations, the inserts really set bits, and the measured rate is a count of wrong answers divided by a count of queries. The double hashing is not a simplification either - deriving k probes from two hashes is the standard Kirsch-Mitzenmacher construction that real implementations use instead of computing k separate digests.

Standing in: the base hash is FNV-1a with MurmurHash3's finalizer, where production would reach for xxHash or MurmurHash3 proper. The keys are generated strings with a regular shape; a structured or adversarial key universe can do worse than anything shown here. And this is a plain Bloom filter - no counting variant, so nothing can be deleted, and no partitioned or scalable variant, so it cannot grow past the size you chose.