Bloom Filters: Membership in a Bit Array

Burton Bloom described this in "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM, volume 13, issue 7, 1970, pages 422 to 426. The structure has not needed changing since.

Allocate a bit array of m bits, all zero, and choose k independent hash functions, each mapping an item to a position in the array.

To add an item, hash it k times and set all k bits. To query an item, hash it k times and check whether all k bits are set. If any bit is zero, the item was definitely never added. If all k are set, it probably was.

That is the entire structure. No items are stored, no buckets, no chaining, no resizing. The array holds nothing but evidence that some items landed on some positions.

Both operations are k hash computations and k bit accesses, independent of how many items are in the filter. There is no degradation as it fills, only a rising error rate.

The one-sided guarantee falls straight out of the mechanics, and it is worth tracing because it explains why nothing can go wrong on that side.

When an item is added, all k of its bits are set to one. Bits are never cleared. So if the item was ever added, all k of its bits are one now, regardless of what happened afterwards.

Therefore, finding any one of the k bits at zero proves the item was never added. A false negative would require a bit to have gone from one back to zero, and nothing in the structure does that.

The converse fails, and that is the source of false positives. All k bits being set does not mean this item set them. They may have been set by k different items, each contributing one bit, none of which is the item being asked about.

So a false positive is a coincidence of coverage, and its likelihood is governed by how much of the array is set, which is the subject of the next step.

The implementation is short enough that the whole thing fits on a screen.

import hashlib, math

class BloomFilter:
    def __init__(self, n, false_positive=0.01, seed=b""):
        # solve the sizing formulas for m and k
        self.m = math.ceil(-n * math.log(false_positive) / math.log(2) ** 2)
        self.k = max(1, round(self.m / n * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)
        self.seed = seed

    def _positions(self, item):
        # two hashes generate k indices: h1 + i*h2 (Kirsch-Mitzenmacher)
        d = hashlib.blake2b(item, key=self.seed[:64]).digest()
        h1 = int.from_bytes(d[:8], "big")
        h2 = int.from_bytes(d[8:16], "big") | 1
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

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

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

bf = BloomFilter(1_000_000, 0.01)
bf.add(b"alice")
b"alice" in bf     # True, always
b"bob" in bf       # False, unless unlucky

Note the hashing trick: rather than computing k independent hashes, two are computed and combined linearly. This is standard, and it does not measurably degrade the false positive rate.

No single item collided with bob. Three different items each set one of the bits bob happens to need, and the filter cannot tell a coincidence of three from a genuine insertion.

That is why the false positive rate depends on the fraction of the array that is set, and not on any pairwise collision between items. More items set more bits; more bits set means a higher chance that any given combination of k positions is fully covered.

It also explains a property that surprises people: the false positive rate rises as the filter fills, and it rises smoothly with no cliff. A filter sized for a million items still works at two million; it simply errs more often. There is no failure mode, only a degrading one, which is unusually forgiving behaviour for a data structure.

The corollary is that a Bloom filter with no size discipline degrades silently. Nothing breaks, so nothing alerts, and the error rate drifts up until someone measures it.

Two formulas govern the design, and both follow from the coverage argument.

After inserting n items into m bits with k hashes, the probability that a specific bit is still zero is approximately exp(-kn/m). A false positive needs all k of the queried bits to be set, so the rate is:

fp  =  (1 - exp(-k*n/m))^k

The choice of k is a genuine trade-off rather than more-is-better. Increasing k means more bits must coincide for a false positive, which helps, and it also sets more bits per insertion, which hurts. Minimising the expression gives:

k* = (m/n) * ln(2)

At that optimum, exactly half the bits are set. That is a satisfying result: the array carries the most information when it is maximally undecided.

Working backwards from a target error rate gives the sizing rule, and it has a useful shape. Reaching 1% needs about 9.6 bits per item, and every additional 4.8 bits per item divides the false positive rate by ten. The cost of accuracy is linear in bits and exponential in the resulting rate.

The obvious way to remove an item is to clear its k bits. It is also obviously wrong, and the reason is the same coincidence that causes false positives.

A bit set by the item being removed may also have been set by another item still in the filter. Clearing it makes that other item's membership test fail, which is a false negative, and false negatives destroy the one property the structure was built around.

Worse, the damage is silent and unbounded. Nothing detects it, and the affected item is one that was legitimately added.

So standard Bloom filters are insert-only. Two variants buy deletion back, and both pay for it.

A counting Bloom filter replaces each bit with a small counter, incremented on insert and decremented on delete. Deletion becomes safe because a shared position stays positive while any owner remains. The cost is the counter width: four bits per slot is common, so the structure is four times larger.

A cuckoo filter stores short fingerprints in buckets with cuckoo hashing, supports deletion, and is competitive on space at low false positive rates. It is more complex and insertion can fail when the table is nearly full.

Bloom filters are unusually widespread, and the deployments share one shape: something expensive sits behind the filter.

Log-structured storage engines. A key lookup may have to check many on-disk files, most of which do not contain the key. Each file carries a Bloom filter over its keys, so the engine skips files whose filter says no. This turns a read that touches many files into one that usually touches one, and it is the single most important use of the structure in practice.

Caches and CDNs. Admitting an object to cache on its first request wastes space on one-hit objects. A filter tracking what has been seen before lets a cache admit only on the second request.

Distributed joins. Sending a filter over one side's keys lets the other side discard non-matching rows before transmitting them, cutting network volume.

The pattern is identical each time. The filter is small enough to sit in memory, the thing it guards is orders of magnitude more expensive, and a false positive costs one unnecessary operation rather than a wrong result.

The first row is the one that causes real incidents. A filter sized for expected load and then handed twice that many items does not fail; it quietly stops being useful, and the symptom is a performance regression with no error anywhere.

The practical defence is to track the fill ratio. Half the bits set means the filter is at its design point. Substantially more means it is past it, and that is a number worth putting on a dashboard, since nothing else will tell you.

Membership is now covered. The next question, counting distinct items, cannot be answered by this structure at all, and needs a completely different idea.