# Bloom filters

> A few bits per item that answer "definitely not" or "probably yes" to set membership.

Concept · Data structures for scale · https://levelcode.org/concepts/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.

> **Interactive: A Bloom filter, bit by bit.** Check names that were never added: most hit at least one 0 bit and are rejected. As the filter fills, more absent names find all their bits set — false positives. A name that was added always passes. Try it: https://levelcode.org/labs/bloom-filter

## Sizing

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

```text
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](https://levelcode.org/concepts/b-tree-vs-lsm-tree)).
- **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](https://levelcode.org/concepts/hyperloglog) and [count-min sketch](https://levelcode.org/concepts/count-min-sketch) for related approximate structures.