Computing

How a Bloom filter says "definitely not" using just a few bits

30seconds
The 30-second version

How can a computer check whether a word is on a huge list using only a few bits per entry? A Bloom filter flips a handful of switches for every word you add, then checks those same switches later.

It can say "definitely not" with total certainty, but "yes" only means probably. Add words, test strangers, and watch false alarms appear as the switches fill up.

Deep dive · 3 min
Deep dive · 3 min

More in Computing

View all →
Why one extra disc doubles the work: the Tower of Hanoi and 2ⁿ − 1 Move a stack of discs between three pegs, never putting a big disc on a small one. It sounds easy, and with 3 discs it is. But every extra disc doubles the… Computing3 min read Why sorting gets slow so fast: bubble sort versus merge sort and n log n Two sorting methods can both be perfectly correct and still differ by a factor of 25,000 on a big list. Race bubble sort against merge sort on the same… Computing3 min read How your phone finds the quickest route: Dijkstra's shortest-path algorithm Your phone finds the fastest route across millions of roads without trying them all. The trick is a rule Edsger Dijkstra devised in 1956: always finish the… Computing3 min read Why eight yes/no answers can draw a fractal, make noise or compute: elementary cellular automata Take a row of lit and dark squares and repeat one tiny rule to make the next row: look at a square and its two neighbours, then decide if it is lit. There are… Computing3 min read Why one flipped bit can be found and fixed: Hamming's error-correcting code A single flipped bit can turn a good file into garbage, yet a machine can find and repair it without ever seeing the original. In 1950 Richard Hamming, tired… Computing4 min read Why swapping cards at random is not a fair shuffle: Fisher–Yates and the 27 paths Shuffling three cards by swapping each one with a random card from the whole row looks fair, but it is not. It makes 3 × 3 × 3 = 27 equally likely paths for… Computing4 min read