Learn · Bloom Filter
Bloom filters
A Bloom filter answers "have I probably seen this before?" using a tiny bit array and a few hash functions — no need to store the items themselves. It can say definitely not or possibly yes, and that "possibly" is the catch: false positives, never false negatives.
Bit array (32 bits)
Add an item
Check an item
Why it's useful
To add an item, hash it k ways and set those bits to 1. To check an item, hash it the same way: if any of those bits is 0 it was definitely never added; if all are 1 it's probably in the set — but other items might have set those same bits, giving a false positive. The pay-off is enormous space saving, which is why databases, caches and crawlers use them to skip expensive lookups. More bits or fewer hashes → fewer collisions. Try adding a few items, then check ones you didn't add until you trip a false positive.