How a Bloom filter says "definitely not" using just a few bits
30seconds
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
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…
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…
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…
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…
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…
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…