THE DATA STRUCTURE PLAYGROUND
Small filter. Big possibility.
Meet the Bloom filter. A space-efficient way to ask, “Have I seen this before?”
Try it yourself, and watch a little bit of math do a lot of work.
Less memory.
More possibility.
More possibility.
A LOOK INSIDE
From an item to a few bits.
Live visualization
YOUR INPUT
applestring
HASH FUNCTIONS Same input, same positions. Every time.
THE BIT ARRAY
0 · empty 1 · set current
Each hash points to one position.24 bits · 3 bytes
INSERTED
Bits in use ▦
0/ 24
0% of the filter is filled
Items inserted ⊞
0
Stored as bits, not as items
False positive chance i
0.0%
Estimated for this configuration
A “no” you can trust.
A “maybe” you can check.
−
At least one bit is 0?
Definitely not in the set. No false negatives.
✓
All the bits are 1?
Possibly in the set. A second check can confirm.
A HAPPY LITTLE COLLISION✧
Sometimes, “maybe”
means “not really.”
Different items can land on the same bits.
That’s a false positive. Let’s make one happen.