Bloom Filter vs Cuckoo Filter: Which Should You Use

A bloom filter and a cuckoo filter are both probabilistic data structures that answer one question cheaply: “have I seen this item before?” Both trade a small, tunable chance of a false positive for dramatic savings in memory compared to storing the actual items, and both answer in constant time regardless of how many items they hold. The difference that usually decides between them is that a cuckoo filter supports deleting an item and a classic bloom filter does not.

How a bloom filter works, briefly

A bloom filter is a bit array plus several independent hash functions. Inserting an item hashes it k times and sets the bit at each resulting position. Checking membership hashes the item the same k ways and checks whether all those bits are set. If any bit is unset, the item was definitely never inserted. If all bits are set, the item was probably inserted — the “probably” comes from the possibility that other insertions happened to set the same combination of bits, a false positive. A bloom filter never produces a false negative: if it says an item isn’t present, it isn’t.

The catch is that bits are shared across every item that hashes into them, so there’s no way to tell which item set a given bit — clearing it to “delete” an item risks breaking membership tests for other items that happen to share that bit. Standard bloom filters simply don’t support removal.

How a cuckoo filter works

A cuckoo filter stores a short fingerprint of each item — a small hash, not the item itself — in one of two candidate buckets determined by hashing the item. Insertion tries to place the fingerprint in either candidate bucket; if both are full, it evicts an existing fingerprint from one bucket and relocates that fingerprint to its own alternate bucket, a chain of displacement borrowed from cuckoo hashing (the same “kick the current occupant to its other slot” idea the name comes from).

Because each bucket holds actual fingerprints rather than shared bits, deletion is straightforward: hash the item to find its candidate buckets, locate its fingerprint, and remove it — a bit in a bloom filter can’t tell you it belongs to a specific item, but a stored fingerprint can. Membership checks work similarly to insertion: hash the item, check both candidate buckets for a matching fingerprint.

Comparing the two

	Bloom filter	Cuckoo filter
Supports deletion	No	Yes
False positives	Yes, tunable rate	Yes, tunable rate
False negatives	Never	Never, unless over capacity
Space efficiency at low false-positive rates	Slightly better	Slightly worse
Space efficiency at very low false-positive rates	Worse	Better
Lookup cost	k hash computations, k bit checks	2 hash computations, 2 bucket checks
Behavior near full capacity	Degrades gracefully	Insertions can fail outright

At very low target false-positive rates (well under 1%), cuckoo filters tend to use less memory per item than bloom filters, in addition to supporting deletion — which is why they’ve displaced bloom filters in some newer systems. At higher false-positive tolerances, the space advantage narrows or reverses depending on implementation details, so the space comparison alone isn’t a clean win for either structure across the board.

Why deletion matters in practice

A bloom filter is a natural fit for data that only grows — a set of already-crawled URLs, a de-duplication filter for a stream that never revisits old items, a first-pass check before a slower database lookup. Real-world use often involves items that need to age out: a cache admission policy that should forget items evicted from the underlying cache, a set of currently-active session tokens, a spam filter that needs to un-flag an address after a false accusation is corrected. A bloom filter handling any of those either needs a workaround — a counting bloom filter, which replaces single bits with small counters so a “delete” can decrement rather than clear, at the cost of more memory per slot — or has to be rebuilt from scratch periodically. A cuckoo filter handles the same requirement natively, with a real delete operation and no extra memory overhead for counters.

Where each shows up

Both structures exist to avoid a much more expensive lookup — hitting disk, querying a remote service, or scanning a full data set — for the common case where the answer is “definitely not present.” A CDN might use one to skip a cache lookup entirely for content it knows was never cached; a database might use one as part of a bloom-filter-backed index to skip reading a data block that provably doesn’t contain a matching key, a pattern related to how a B-tree index narrows a search before touching disk. Distributed systems checking whether a key might exist on a remote shard before making a network round trip are another common home for either structure — the choice usually comes down to whether the set of keys being tracked needs to shrink over time.

The takeaway

Both bloom filters and cuckoo filters answer set-membership questions in constant time and constant memory, with a tunable, nonzero chance of a false positive but never a false negative. The deciding factor is usually whether items need to be removed: a bloom filter is simpler and works well for append-only or periodically-rebuilt sets, while a cuckoo filter’s fingerprint-and-bucket design supports real deletion and tends to be more space-efficient at very low false-positive rates — at the cost of insertions that can occasionally fail once the structure gets too full.