Bloom Filter Visualization | Hashes, Bits, False Positives

The idea: a few bits that say "no" for sure

A Bloom filter answers one question: "have I seen this key?" It stores no keys at all, only an array of m bits, and uses k hash functions to pick k of them per key. It can say definitely not or probably yes. It is never wrong about "no", and sometimes wrong about "yes".

The word cat goes through three hash functions h1, h2 and h3, which give 7, 4 and 1. Arrows point from each hash to bits 7, 4 and 1 of a 16-bit array, which are set to 1; all other bits stay 0 — add("cat") with m = 16 and k = 3: three hashes, three bits set to 1, and the word itself is not stored.

The page has one filter of m = 16 bits and k = 3 hashes (1 or 6 in the k select). Pick a word and press Add or Query. Each hash value is shown with an arrow to its bit. The real set below the filter keeps the words actually added, so every answer is checked against the truth. Under each bit are the words that need it.

add and mightContain

add(x): compute h1(x) … hk(x) and set those k bits to 1. A bit that is already 1 stays 1.
mightContain(x): compute the same k positions. If any bit is 0, x was never added: definitely not. If all are 1: probably yes.

Adding cat, dog and owl sets 8 of the 16 bits; dog's bits are all 1, so it is found (Demo 1). fox maps to bits 14, 1 and 4, and bit 14 is still 0, so fox is definitely not there (Demo 2). Since add() only turns bits on, a member's bits stay 1 forever: there are no false negatives.

The page makes the k positions with double hashing: a = FNV-1a(x) mod 16, b = (djb2(x) mod 16) | 1, and h_i = (a + (i−1)·b) mod 16. Two real hashes are enough to make k good ones (Kirsch and Mitzenmacher). Making b odd keeps the k positions different.

False positives, and the formula

A false positive is a key that was never added, but whose k bits were all set by other keys. The more keys, the more bits are 1, and the likelier that is. After n keys, the chance is about

p \approx {(1 - e^{- k n / m})}^{k}

The fill ratio (bits set ÷ m) tells you where you are: a query of a new key is a false positive with probability about fill^k. In Demo 3, fox is "definitely not" after cat, dog and owl. Then ant and elk set bits 14 and 15, and fox becomes a false positive. With n = 5 and 12 of 16 bits set, the formula says 22.5%; the page saw 1 false positive in 3 non-member queries.

Two rows of 16 bits. Before: cat, dog and owl set 8 bits; fox checks bits 14, 1 and 4, and bit 14 is 0, so definitely not. After ant and elk are added, 12 bits are set; bit 14 is now 1, so all of fox's bits are 1 and the filter wrongly says probably yes — The same query, before and after two more words: one bit flips to 1 and "definitely not" becomes a false positive.

Why you cannot delete

A bit does not know which keys set it. To delete dog you would clear bits 9, 8 and 7, but cat needs bit 7 too. Now cat's check finds a 0 and the filter says "definitely not" about a member: a false negative, the one mistake a Bloom filter must never make (Demo 4). The page shows the broken bit with the name under it in red.

A counting Bloom filter fixes this: each position holds a small counter (often 4 bits) instead of a bit. add() adds 1, delete() subtracts 1, and a position counts as set while it is above 0. It costs about 4 times the memory. Cuckoo filters are another option that supports deletes.

Choosing m and k

More hashes mean each query checks more bits, which helps, but each key also sets more bits, so the filter fills faster. With few hashes, one shared bit is enough to fool it: with k = 1, gnu lands on bit 7, which cat set, and is a false positive (Demo 5). The formula for m = 16:

k	n = 3: bits set by cat, dog, owl	n = 3: formula	n = 5: formula
1	3	17.1%	26.8%
3	8	8.0%	22.5%
6	12	9.5%	36.8%

The best k is (m/n)·ln 2, which leaves about half the bits set. For a target false-positive rate p, the bits needed are m = −n·ln p / (ln 2)²: about 9.6 bits per key for 1% and 14.4 for 0.1%, whatever the size of the keys. That is why real filters use thousands of bits, not 16.

A real use: skipping disk reads in an LSM tree

An LSM tree (RocksDB, LevelDB, Cassandra) keeps its data in many sorted files on disk, the SSTables. A point read may have to look in each of them. Every SSTable carries a Bloom filter of its keys, kept in memory. get(key) asks the filter first and reads the file only on "probably yes".

get(key) checks the SSTable's Bloom filter in memory. Definitely not: skip the file, no disk read. Probably yes: read the block from disk; either the key is found, or it is not there and the read was wasted because of a false positive — The filter turns most reads of missing keys into no I/O at all; only false positives cost a wasted read.

In Demo 6, SSTable-1 holds cat, dog, owl, ant and elk. get("bee") is skipped (bit 0 is 0), get("dog") reads the block and finds it, and get("fox") reads it for nothing: 2 disk reads, 1 wasted, 1 skipped. RocksDB's default is 10 bits per key, about a 1% false-positive rate. See LSM Tree vs B+ Tree for the whole read and write path, Open Hash Tables for a structure that stores the keys and has no false positives, and Merkle Trees for Anti-Entropy Repair for another way of using hashes to avoid reading data.

To keep a fair random sample of a stream instead of a membership summary, see reservoir sampling.

Give each position a full counter and one hash per row and you get a Count-Min Sketch, which estimates how often each key was seen.

Cuckoo filters store fingerprints in a cuckoo hash table; see Cuckoo Hashing.

What the page leaves out

Real sizes (thousands to millions of bits) and real hash functions such as MurmurHash or xxHash; blocked and cache-line Bloom filters that keep a key's bits in one cache line; scalable Bloom filters that grow; cuckoo, quotient and ribbon filters; and how RocksDB stores one filter per data block or partition and sets bits per key per level.