Bloom filter

A membership test that keeps no members. Ask it whether something is in the set and it answers either “definitely not” or “probably yes” — and it is only ever wrong in the second direction.

Where this is actually used

Cassandra, HBase and LevelDB keep one of these in memory for every file on disk. Before reading a file to look for a key, they ask the filter first. A “no” is proof, so the read is skipped outright; a “yes” costs one read that may find nothing. Most of the disk traffic disappears, and because a “no” is never wrong, no key is ever missed.

The guarantee

An inserted item can never answer “not present” — insertion only sets bits, and nothing ever clears them. This is structural, not statistical: not almost never, never.

How it works

m bits, k hashes. Insert sets k bits. A query answers “possibly present” only if all k are set.

Burton H. Bloom, CACM 13(7), 1970

Start hereDrag the memory slider to the left until the false-positive rate starts climbing — then look at the false-negative count beside it. It stays at zero the whole way down.

One item, all the way through

Before any of the controls below: this is the whole mechanism, at a size you can count. 64 bits, 3 hashes, starting empty.

1 of 12

The item is hashed twice

item-0 → h₁ = 3,357,449,650, h₂ = 2,355,847,969

Two 32-bit numbers, from MurmurHash3 with two different seeds. Same item, same numbers, every time and on every machine — that determinism is what makes it possible to ask about the item again later.

k slot numbers come from those two

slots this item addresses
g₀	(3,357,449,650 + 0×2,355,847,969) mod 64	= 50	newly set
g₁	(3,357,449,650 + 1×2,355,847,969) mod 64	= 19	newly set
g₂	(3,357,449,650 + 2×2,355,847,969) mod 64	= 52	newly set

gᵢ(x) = h₁(x) + i·h₂(x), taken mod m so it lands inside the array. Two hashes give k of them: Kirsch & Mitzenmacher (ESA 2006) showed these behave like k independent hashes, which is why the error bounds still hold.

Those bits are set · 3 bits set

0000000000000000000100000000000000000000000000000010100000000000

Nothing is ever cleared. That is the whole reason an inserted item can never come back “not present”.

Use a deliberately bad hash

Stream

Distributionhow often items repeat — real data is never uniformEvery item equally likely. The case the textbook bounds are stated for.

Distinct itemshow many different items exist to draw fromStream lengthhow many items go through the structureSeedchanges the hash, and therefore which items happen to collide

k — hasheshow many places in the array each item is recordedk = (m/n)·ln 2

The link carries the stream and every parameter. No server, no account — the state travels in the URL.

Memory

how much memory the filter gets — more bits, fewer wrong answers

m — bits65,536 bits · 8.0 KiB

Drag to resize the bit array. Predicted and measured error move together.

Is that number surprising?

The measured rate above is one draw. Here is the same configuration run 24 times, each with a different seed — a different stream and a different set of probes, which is what the “seed +1” button does one press at a time.