Bloom filters

"Definitely not" is valuable

A Bloom filter answers "is this item in the set?" using a tiny bit array instead of storing the items. It can say"definitely not" or "probably yes". It never misses an item that was added, but it sometimes says yes to one that wasn't (a false positive). In exchange it uses a few bits per item, a tiny fraction of the space the items themselves would take.

How it works

1. Start with m bits, all 0, and pick k hash functions.
2. Add an item: hash it k ways and set those k bits to 1.
3. Check an item: if any of its k bits is 0, it was never added. If all are 1, it probably was, though other items may have set those bits.

Try it

32 bits, 3 hash functions. Add a few animals, then check words you didn't add. As the bits fill up you'll eventually hit a false positive.

The false-positive rate is about (1 − e−kn/m)k. With about 10 bits per item and 7 hash functions it's roughly 1%. You can't delete items from a basic Bloom filter, since clearing a bit could erase other items too.

Where it's used

• Databases (Cassandra, RocksDB, HBase): skip reading files from disk that definitely don't contain a key.
• Web crawlers: "have I already visited this URL?" for billions of URLs.
• Username availability or malicious-URL checks: a fast first filter before the exact (slower) lookup.
• Caches: avoid caching items that are only ever requested once.