Bloom & Cuckoo Filters

How Bloom filters work

A Bloom filter is a bit array of m bits, paired with k independent hash functions. To insert an item, you hash it with each of the k functions and set the corresponding bits to 1. To check membership, you hash again and check if all k bits are set. If any bit is 0, the item is definitely not in the set. If all bits are 1, the item is probably in the set — but it might be a false positive.

Why false positives happen

As more items are inserted, more bits get set. Eventually, for a given non-member, all k of its hash positions might coincidentally already be set by other insertions. The theoretical false positive rate is (1 - e-kn/m)k, where n is the number of items. Add enough items above and watch the rate climb — then try looking up items you never inserted.

Why you can't delete

Unsetting a bit would break things. If two items share a hash position (which is expected), clearing that bit when you "delete" one item would also remove the other. There's no way to know how many items map to each bit, so deletion is off the table.

Where you'll find them

Bloom filters are everywhere: LSM-tree storage engines (LevelDB, RocksDB, Cassandra) use them to skip unnecessary disk reads. CDNs use them to avoid caching one-hit-wonder URLs. Spell checkers, safe browsing lists, Bitcoin SPV nodes checking if a transaction matches a filter — any time you need a fast "definitely not" answer, a Bloom filter is a good fit.

How Cuckoo filters work

Instead of a flat bit array, a Cuckoo filter stores short fingerprints (a few bits of the hash) in a table of buckets. Each bucket holds a fixed number of slots. An item can live in one of two candidate buckets — its primary bucket (from hashing) or its alternate bucket (from XORing the primary with the hash of the fingerprint).

The cuckoo hashing trick

When both candidate buckets are full, the filter evicts an existing fingerprint to its alternate bucket — like a cuckoo bird pushing another bird's egg out of the nest. That displaced fingerprint might trigger another eviction, creating a kick chain. If the chain exceeds a maximum length (typically 500 kicks), the insert fails — the filter is too full.

Why deletion works

Because each slot stores a fingerprint, you can identify and remove a specific item. Find the fingerprint in either candidate bucket and clear that slot. Unlike Bloom filters, this doesn't affect other items — each slot belongs to one fingerprint.

Trade-offs vs. Bloom

Cuckoo filters support deletion, which Bloom filters can't. For the same false positive rate, they often use comparable or less space. The downside: inserts can fail at high load factors (typically >95%), and the kick chain adds occasional latency spikes. Bloom filters never fail to insert.

Where you'll find them

Packet classification in network switches, deduplication systems, key-value store membership checks, and anywhere you need the space efficiency of a Bloom filter but also need to remove items.