Bloom filters

A Bloom filter is a compact, probabilistic set. It answers "is x in the set?" with either definitely not or probably yes, using a few bits per item regardless of how large the items are. False positives are possible; false negatives are not.

#How it works

The filter is an array of m bits, all zero, and k hash functions.

• Add x: compute the k hashes of x, each giving a bit position, and set those bits to 1.
• Check x: compute the same k positions. If any bit is 0, x was never added. If all are 1, x was probably added — or other items happened to set those bits.

You can't remove items (clearing a bit might remove others too); counting Bloom filters and cuckoo filters support deletion at more cost.

#Sizing

With n items, m bits and k hashes, the false-positive rate is about:

p ≈ (1 − e^(−k·n/m))^k        optimal k = (m/n) · ln 2
bits per item for a target p:  m/n ≈ −ln(p) / (ln 2)²   → ~9.6 bits for 1%, ~14.4 bits for 0.1%

A filter of 10 million items at 1% false positives needs about 12 MB — far smaller than the items themselves.

#Where they're used

• LSM-tree databases keep one per SSTable so reads skip files that can't contain a key (B-trees vs LSM-trees).
• Rejecting unknown keys cheaply, such as nonexistent short links probed by scanners, before touching a cache or database.
• "Have we seen this?" checks: crawled URLs, already-recommended items, one-time tokens (with an exact check after a positive).
• Reducing network traffic: send a filter instead of a full set, and ask for details only on positives.

The rule that makes them safe: act on "definitely not" directly, and treat "probably yes" as a hint to do the exact (more expensive) check. See HyperLogLog and count-min sketch for related approximate structures.