A Bloom filter is a compact, probabilistic set. It answers one question — “have I possibly seen this key?” — using far less memory than storing the keys themselves.

It's a bit array of m zeros plus k independent hash functions. To add a key, hash it k ways and set those k bits to 1. To test a key, hash it the same k ways: if any of those bits is 0 it is definitely absent; if all are 1 it is probably present.

That asymmetry is the whole point. False negatives are impossible, but false positives happen because unrelated keys can collectively light up the same bits. The false-positive rate rises as the array fills, and you trade it off against m and k up front.

Reach for one as a cheap gate in front of something expensive: skip a disk or network lookup when the filter says “definitely not there.” LSM-tree databases put a Bloom filter on each SST file for exactly this reason.

The catch: a classic Bloom filter can't delete or count, and it can't enumerate its members. If you need deletion, look at a counting or cuckoo filter instead.

Think of a Bloom filter as a membership test that's allowed to say “maybe.” It never forgets something you added, but it will occasionally claim to recognize something you didn't.

Under the hood it's just a row of bits and a handful of hash functions. Adding an item flips a few bits on; checking an item asks whether those same bits are all on.

Because different items can flip overlapping bits, an “all on” result isn't proof — it's a strong hint. A “not all on” result, though, is a guarantee the item was never added.

The practical win is memory. You can represent millions of items in a few megabytes and get near-constant-time checks, which is why caches, databases, and crawlers use them to avoid pointless work.

Just remember the limits: you can't remove items or ask what's inside, and you must size it for your expected item count or the false-positive rate creeps up on you.