Bloom filters have long been the go-to probabilistic data structure for membership testing, but they come with well-known limitations: no deletion support, suboptimal space efficiency at low false positive rates, and cache-unfriendly memory access patterns. Two modern alternatives—cuckoo filters and xor filters—address these shortcomings with different trade-offs.

How Cuckoo Filters Work

Cuckoo filters borrow the core idea from cuckoo hashing: each item can live in one of two possible buckets, determined by two hash functions. Instead of storing the full item, each bucket holds a small fingerprint (typically 4-16 bits). When both buckets are full, the filter kicks out an existing fingerprint and moves it to its alternate location, potentially triggering a chain of displacements.

The key advantage is deletion. Because fingerprints are stored explicitly in buckets, you can remove an item by locating and clearing its fingerprint. This makes cuckoo filters suitable for caches, blacklists, and any system where entries expire or get invalidated. They also offer better space efficiency than bloom filters at false positive rates below 3%, and their bucketed structure improves cache locality.

The downside is complexity. Insertion can fail if the filter enters a cycle during displacement, forcing a rebuild. While rare with proper load factor management (typically 95% occupancy), this adds operational overhead that bloom filters never face.

Xor Filters: Static and Compact

Xor filters take a radically different approach. They’re constructed offline using a 3-graph peeling algorithm that assigns each item to three possible locations, then solves a system of XOR equations to determine what value to store at each position. The result is a static, immutable filter that cannot be modified after construction.

The payoff is space efficiency. Xor filters use roughly 9.84 bits per item regardless of the target false positive rate, significantly beating both bloom filters and cuckoo filters at low error rates. They also guarantee constant-time lookups with exactly three memory accesses, making performance predictable.

The construction algorithm is more expensive than simply inserting into a bloom filter—it requires multiple passes and can occasionally fail, requiring a rebuild with different hash seeds. But for read-heavy workloads with infrequent updates, this one-time cost is negligible. Xor filters shine in scenarios like static asset catalogs, immutable dataset indexes, or any application where the set membership is known upfront and doesn’t change frequently.

When to Use Each

Bloom filters remain the right choice for simplicity and when you need continuous incremental updates without reconstruction. Their insert-only model is straightforward and their behavior is well-understood in production.

Use cuckoo filters when you need deletion or operate at false positive rates below 3%. They’re ideal for dynamic blacklists, cache admission policies, or any system where set membership changes frequently and you can’t afford to rebuild from scratch.

Choose xor filters when the dataset is mostly static and space efficiency matters. They’re perfect for embedding in binaries, distributing with software packages, or building indexes for immutable data. Their predictable performance and minimal memory footprint make them attractive for memory-constrained environments.

Implementation Considerations

All three filters require careful tuning. Cuckoo filters need appropriate bucket sizes and load factors to avoid insertion failures. Xor filters need enough RAM to hold the construction graph, which can be 2-3x larger than the final filter during building. And bloom filters, despite their simplicity, still need proper hash function selection and bit array sizing to hit target error rates.

Modern implementations of both alternatives exist in production: cuckoo filters appear in network switches and CDN edge nodes, while xor filters power search indexes and static analysis tools. The choice depends on your workload characteristics, but neither is a universal replacement for bloom filters—they’re specialized tools that excel in specific contexts where bloom filters fall short.