Bloom filters

A Bloom filter answers one question: "is this item possibly in the set?" It uses a row of bits (a bit array) and a few hash functions, which turn an item into positions in that row. It needs a tiny fraction of the memory a real set would.

Adding an item sets k bits to 1. Checking an item tests those same k bits. If any bit is 0, the item is definitely not there.

If all are 1, it is probably there. The chance of a wrong "yes", a false positive, depends on how big you make the array: for example, about 1% at under 10 bits per item. It never gives a wrong "no" (a false negative), and a basic one cannot delete items.

Databases such as Cassandra use them to skip disk files that cannot contain a key. Web crawlers use them to avoid revisiting URLs. Use one only where an occasional false positive is cheap.