Bloom Filter

A space-efficient probabilistic set that answers membership with no false negatives and a tunable false-positive rate.

What it is

A Bloom filter represents a set using a bit array of m bits and k independent hash functions. To add an element, hash it k ways and set those k bits. To test membership, check whether all k bits are set: if any is zero the element is definitely absent; if all are set the element is probably present. There are no false negatives, only false positives.

Tuning

Kronos motion — space economy

For n inserted elements, the false-positive probability is approximately (1 - e^(-kn/m))^k. The optimal number of hashes is k = (m/n) * ln 2, giving a false-positive rate near 0.6185^(m/n). Choosing about 10 bits per element yields roughly a 1 percent false-positive rate, far smaller than storing the elements themselves.

Core operations

python

import mmh3   # any good hash works

class BloomFilter:
    def __init__(self, m, k):
        self.m, self.k = m, k
        self.bits = bytearray(m // 8 + 1)
    def _idx(self, item, i):
        return (mmh3.hash(item, i) % self.m)
    def add(self, item):
        for i in range(self.k):
            b = self._idx(item, i)
            self.bits[b >> 3] |= (1 << (b & 7))
    def __contains__(self, item):
        return all(self.bits[(b := self._idx(item, i)) >> 3] & (1 << (b & 7))
                   for i in range(self.k))

Variants

Counting Bloom filters use small counters instead of bits to support deletion.
Scalable Bloom filters grow as more elements are added while holding the error bound.
Cuckoo filters allow deletion and often use less space at low false-positive rates.
Quotient filters and the TinyLFU sketch apply similar ideas to frequency estimation.

Where it is used

Databases use Bloom filters to skip disk reads for keys not present in an SSTable; web caches and CDNs use them to avoid caching one-hit items; distributed systems use them to reduce network lookups. The pattern is: a cheap in-memory test that rules out the common negative case before an expensive exact check.