Bloom Filter

A Bloom filter answers set membership with two answers instead of one: a confident definitely not, or an uncommitted maybe. It never says a plain yes. In exchange for the uncertainty it stores almost nothing: no words, only a row of bits.

The figure above runs one with sixteen bits and three hash functions. Three words are already in: apple, banana, and cherry. Press play and the figure queries lime, a word nobody added. Watch what the filter gets wrong, then read on to see why that wrong answer is the point.

Adding a word sets three bits

To add a word, the filter hashes it three times. Hash functions h₁, h₂, and h₃ each map the word to one position in the bit array, and the filter sets those bits to 1. That is the entire insert. The word itself is never stored, which is why the filter stays small, and also why it can never list its contents.

Try it in either figure. Type kiwi and press Add. The badges read h₁ → 11, h₂ → 14, and h₃ → 2, and a line drops from each badge to its cell. Bit 14 was already 1, because banana set it earlier. Shared bits are normal, and they are where the maybe comes from.

A query reads the same three bits

A query runs the same three hashes and reads the bits instead of writing them. If any checked bit is 0, the word was never added. Had the word been added, that bit would be 1, and bits are never cleared. This answer is exact. If every checked bit is 1, the answer is maybe. The word might be in, or other words might have covered its bits.

Query mango in the figure. The first check reads bit 3 and finds a 1, set by apple. The second check reads bit 2 and finds a 0, and the filter stops there. One 0 is proof, so the third bit is never read.

The other direction is guaranteed. Add kiwi, then click its chip under the array. All three checks read 1, because the add set those bits and nothing ever clears a bit. A member always reads maybe. Bloom filters have false positives, but never false negatives.

The whole data structure fits in one class. The hash functions differ from the figure's, but the shape is the same. The implementation panel below carries this class in Python and JavaScript:

class BloomFilter:
	def __init__(self, m=16, seeds=(1, 2, 3)):
		self.bits = [0] * m
		self.m = m
		self.seeds = seeds

	def _positions(self, word):
		for seed in self.seeds:
			h = seed
			for ch in word:
				h = (h * 131 + ord(ch)) % (1 << 32)
			yield h % self.m

	def add(self, word):
		for pos in self._positions(word):
			self.bits[pos] = 1

	def __contains__(self, word):
		return all(self.bits[pos] for pos in self._positions(word))

Where the maybe comes from

Bits are shared, and a bit does not record who set it. So a word that was never added can find all of its bits on, when other words happen to cover them. That is a false positive: a maybe for a word that was never added.

The figure above opens on exactly that case. lime hashes to bits 4, 14, and 7:

1. h₁ maps lime to bit 4. It reads 1, set by apple and cherry.

2. h₂ maps lime to bit 14. It reads 1, set by banana.

3. h₃ maps lime to bit 7. It reads 1, set by banana again.

Three 1s for a word nobody added, so the filter answers maybe. The figure below replays the query. Then try to fool the filter yourself. Add words and watch the array fill: the fuller the array, the more often a maybe lies.

Sizing the filter

The maybe rate is a dial, not fate. Three numbers set it: m the number of bits, n the number of words you plan to add, and k the number of hash functions. The false-positive rate is approximately (1 − e^(−kn/m))^k, where kn/m measures how full the array is.

The knobs behave the way you would hope. More bits per word push the rate down. More words into the same array push it up. The hash count has a sweet spot. Too few, and one shared bit can fake a match. Too many, and every query needs a crowded row of 1s. For a given m and n, the best k is (m/n) ln 2. The figure below plots the rate against k for the current m and n, so drag the sliders and watch the sweet spot move.

With k at its best value, the rate falls off fast:

Ten bits per word buys a wrong maybe about once in 125 queries. The demo filter is small on purpose. Sixteen bits for three words with k = 3 gives a maybe rate near 8%, so false positives show up within a few tries instead of once in a hundred.

What a Bloom filter cannot do

Three limits follow straight from the design:

• Delete. Clearing a word's bits can clear bits that other words share, so removal is unsafe. When deletes matter, a counting Bloom filter swaps each bit for a small counter.

• List. The words were never stored, so there is nothing to enumerate.

• Confirm. The filter has no plain yes. When an exact answer matters, a maybe must be checked against the real data.

Where it earns its keep

A Bloom filter earns its keep as a screen in front of an expensive check. The cheap filter answers most queries with a fast definitely not, and only the maybes pay for the slow lookup. Keep the filter in memory while the real data sits on disk, and almost every miss skips the disk.

• Storage engines such as RocksDB and Cassandra keep a Bloom filter per data file, so a read for a missing key never opens the file.

• CDNs screen one-hit wonders: a URL is cached only after the filter says it was requested before.

• Breach-password checks answer against huge lists that never ship to the device.

Keep the two answers straight and the practice problems below get easier: a 0 bit is a proof, and a 1 bit is only a rumor. Each one is membership in disguise. Solve it with a hash set first, then ask what a bit array would trade.