Bloom vs Cuckoo Filters: Choosing the Right Probabilistic Data Structure

Bloom filters and Cuckoo filters are two probabilistic data structures used to efficiently test whether an element belongs to a set, but they differ in implementation, performance characteristics, and usage scenarios.

1. Bloom Filter

The principle of a Bloom filter is to apply n hash functions to a key, obtaining n positions in a bit array and setting those bits to 1.

When querying, the same hash functions are applied; if any of the corresponding bits is 0, the element is definitely not in the set. If all bits are 1, the element may be present, leading to false positives.

False positives occur because different elements can set the same bits. Increasing the number of hash functions reduces the false‑positive rate at the cost of higher computation and space usage.

Bloom filters have limitations: they do not support deletion of elements, and their space utilization is relatively low.

2. Cuckoo Filter

Unlike Bloom filters, Cuckoo filters support deletions and dynamic insertions with higher efficiency.

The underlying structure is an array of buckets; each bucket can store a configurable number of fingerprints (e.g., four).

2.1 Bucket Position Calculation

Insertion uses two dependent hash functions to compute the two candidate buckets. The first hash gives h1 (first bucket index); the second bucket index h2 is obtained by XOR‑ing h1 with the hash of the fingerprint.

2.2 Adding Elements

The fingerprint of the element is computed first. The two candidate buckets are derived as described. If either bucket has free slots, the fingerprint is stored there (randomly chosen if both are free).

If one bucket is full and the other has space, the fingerprint is placed in the available bucket.

If both buckets are full, a random fingerprint in one bucket is evicted, re‑inserted into its alternate bucket, possibly triggering further evictions (capped by a configurable recursion limit).

2.3 Querying Elements

To query, the two candidate buckets are examined; if any fingerprint in those buckets matches the element’s fingerprint, the element is considered present (subject to false positives).

2.4 Fingerprint Distribution

Multiple identical fingerprints can reside in the same bucket or across different buckets, which may increase false‑positive probability.

2.5 Deleting Elements

Deletion removes the fingerprint from its bucket(s). If multiple identical fingerprints exist, all copies are removed.

Conclusion

Both Bloom filters and Cuckoo filters have distinct advantages and suitable scenarios:

If you need a simple, mature probabilistic structure without deletion support, Bloom filter is a good choice.

If you require deletions and stricter false‑positive rates, Cuckoo filter may be preferable.

Choosing the right data structure depends on the specific application requirements and performance constraints.