How a Bloom Filter Trades Bits for a False-Positive Rate

A membership test against a million keys needs either the keys themselves or something derived from them. A hash table keeps the keys, at a cost of at least eight bytes per entry plus the slack imposed by the load factor, so a million short strings occupy tens of megabytes. A Bloom filter answers the same question from an array of bits with no keys stored at all: about ten bits per key, roughly 1.2 MB for the million, and an error rate near one percent. The error is one-sided — a filter never denies a key it has seen — and that asymmetry is the whole basis of its usefulness. A positive answer means “probably”, a negative answer means “certainly not”, and the probability is a function of nothing but the number of bits and the number of distinct keys.

Two operations on a bit array

The structure is an array of $m$ bits, initialised to zero, and $k$ hash functions that each map a key uniformly onto the range $[0, m)$. Insertion computes all $k$ positions and sets those bits. Lookup computes the same $k$ positions and tests them. If any bit is zero the key was never inserted; if all $k$ are one, the key is either present or the bits were set by other keys. There is no third state and no stored key, so the space is exactly $m$ bits regardless of whether keys are 8-byte integers or kilobyte paths.

The absence of false negatives follows directly: inserting a key sets every bit that a later lookup of that key will test, and nothing in the structure ever clears a bit. The absence of false positives does not follow, and the rest of the design is about bounding how often they occur.

Two numbers fix the shape of the structure. The first is the bit budget per key, $m/n$, where $n$ is the expected number of distinct insertions. The second is $k$, which is not free: each lookup costs $k$ memory probes, and those probes dominate the runtime because each one is likely to be a cache miss rather than an arithmetic operation.

Where the false-positive probability comes from

Consider one bit after $n$ insertions of $k$ hash values each. A single hash value lands on that bit with probability $1/m$, so it misses with probability $1 - 1/m$. Across $kn$ independent placements the bit remains zero with probability

$$ \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m} $$

The approximation is accurate for the sizes that matter: at $m = 10^7$ the two expressions differ in the fourth decimal place. A lookup of an absent key tests $k$ bits that are all one with probability

$$ \varepsilon \approx \left(1 - e^{-kn/m}\right)^{k} $$

That is the entire error analysis, and it depends on an assumption worth stating: the $k$ positions are independent and uniform. Real hash functions are deterministic, so the assumption is a modelling claim about their output distribution, not a property that can be proved about any particular function. When it fails, the measured rate exceeds the formula, sometimes by a wide margin.

The formula also assumes the filter was sized for the number of keys it actually received. It has no way to detect that it was not.

Choosing k and m for a target error

Treating $\varepsilon$ as a function of $k$ for fixed $m/n$, the minimum sits where the derivative vanishes:

$$ k = \frac{m}{n}\ln 2 \approx 0.693,\frac{m}{n} $$

Substituting that $k$ back gives $\varepsilon \approx 2^{-k} \approx 0.6185^{m/n}$. Both forms are useful. The first says how many probes to perform; the second says how many bits each halving of the error rate costs — about $1/\ln 2 \approx 1.44$ bits per key per halving. To reach one percent, invert the relation: $m/n = \log_2(1/\varepsilon)/\ln 2 \approx 9.6$ bits per key, with $k = 7$ for $m/n = 9.6$ rounded to an integer. A tenth of a percent needs about 14.4 bits and ten probes.

Bits per key	Optimal k	Approximate error
6	4	5.6%
8	6	2.2%
10	7	0.8%
12	8	0.3%
14	10	0.12%
16	11	0.05%

The curve near the optimum is flat. At $m/n = 10$, using $k = 5$ instead of the optimal 7 raises the error from roughly 0.82% to roughly 0.94%, while cutting probe work by nearly a third. Implementations that favour lookup speed routinely choose $k$ below the optimum for this reason, and the loss is small enough that the choice is defensible. What is not defensible is choosing $k$ far above the optimum: the error rises again, because the array saturates and every probe tests a bit that other keys have already set.

Why the filter cannot forget

Deleting a key would require clearing its $k$ bits, and those bits are shared with every other key that hashed to the same positions. Clearing them introduces false negatives for keys that are still present, which breaks the one guarantee the structure offers. A Bloom filter is therefore an insert-only structure, and its error rate is a function of the total number of insertions since construction, not the number of live entries.

This makes the filter a poor fit for any workload with churn. A cache index that admits and evicts entries will see its bit array fill with the residue of departed keys; the false-positive rate climbs toward one and the filter stops discriminating. The standard responses are to rebuild periodically from the live set, or to use a counter per position so that removal becomes possible — the subject of counting Bloom filters.

Saturation is also why oversizing the key count is not a harmless precaution in the other direction. The error is exponential in $n$ for fixed $m$. A filter built for one million keys at ten bits per key has an error near 0.8%. Load two million keys into it and the exponent doubles: with $k = 7$ and $m/n = 5$, the error becomes $(1 - e^{-7/5})^7 \approx 14%$. A factor-of-two sizing error turns a usable filter into a coin flip.

What a probe actually costs

The arithmetic per lookup is a handful of multiplications and shifts. The cost that matters is memory: $k$ positions scattered uniformly over $m$ bits are $k$ independent cache lines. A 64-byte line holds 512 bits, so a 1.2 MB filter spans roughly 20,000 lines, far more than an L1 cache holds and comparable to the size of an L2. Each lookup therefore issues several misses, and their latencies can exceed the arithmetic by two orders of magnitude.

Two consequences follow. First, the effective cost of a filter is closer to $k$ memory references than to $k$ hash evaluations, so reducing $k$ below the optimum is often a net win, and confining the $k$ probes to one or two cache lines is a larger win still. Blocked layouts that fit all probes for a key into a single 64-byte block cut the reference count from $k$ to one while leaving the leading error term unchanged; the trade they actually make is a small probe-duplication penalty and an extra format parameter, examined in blocked and partitioned layouts. Second, computing $k$ independent hashes of a long key can itself dominate, which is why practical filters derive all $k$ values from one or two hash words rather than running $k$ hash functions. The derivation and its failure modes are covered in deriving k probes from two hash words.

A minimal implementation

The code below keeps the two operations separate and sizes itself from a target error. The modulus is a power of two, so the reduction is a mask; the second hash word is forced odd so that the probe sequence visits the full range when $m$ is a power of two.

import hashlib, math

class Bloom:
    def __init__(self, n, fp=0.01):
        # m = -n ln(fp) / (ln 2)^2 minimises bits for the target error
        self.m = 1 << max(3, math.ceil(math.log2(-n * math.log(fp) / (math.log(2) ** 2))))
        self.k = max(1, round(self.m / n * math.log(2)))
        self.bits = bytearray(self.m // 8)

    def _positions(self, key):
        h = hashlib.blake2b(key, digest_size=16).digest()
        h1 = int.from_bytes(h[:8], 'little')
        h2 = int.from_bytes(h[8:], 'little') | 1      # odd, so gcd(h2, m) == 1
        for i in range(self.k):
            yield (h1 + i * h2) & (self.m - 1)

    def add(self, key):
        for p in self._positions(key):
            self.bits[p >> 3] |= 1 << (p & 7)

    def maybe_contains(self, key):
        return all(self.bits[p >> 3] >> (p & 7) & 1 for p in self._positions(key))

Rounding $m$ up to a power of two wastes at most a factor of two in space, which is a real cost at these densities: at ten bits per key, rounding 9.6 up to 16 bits per key doubles the memory for no reduction in error beyond what the extra bits already buy. Implementations that care about the last few percent keep $m$ arbitrary and pay a division, or choose $m$ as a prime.

Where the structure earns its place

The filter is at its best when the negative answer is the common case and the cost of a false positive is a wasted lookup rather than a wrong result. Read paths in log-structured storage consult a filter per level before touching disk, so a negative answer avoids an I/O of tens of microseconds at the cost of a few nanoseconds of probing. Distributed caches use a filter to decide which nodes hold a key, avoiding a broadcast. Neither use tolerates a false negative, and neither needs deletion from the filter itself.

The failure modes are equally consistent: sizing for the wrong key count, churn without rebuild, hash functions whose output is not uniform over the range, and serialised filters read back with a different $m$ or $k$ than they were built with. The last is the quietest, because the structure has no header of its own and a mismatched reader will happily probe the wrong bits.