Understanding Bloom Filters, Counting Bloom Filters, and Cuckoo Filters

IO bottlenecks are common in backend systems, especially when many requests trigger unnecessary database queries; filters such as Bloom filters can pre‑check whether a key is likely present before hitting the database.

Bloom Filter uses a bitmap and multiple hash functions: each incoming element sets several bits to 1; a later query hashes the same way and checks those bits—if any are 0 the element is definitely absent, otherwise it may be present (possible false positives).

The basic Bloom filter suffers from two main issues: (1) false positives increase as more elements are added, and (2) it cannot delete elements because clearing bits may affect other items.

Counting Bloom Filter replaces the bitmap with an array of counters; each insertion increments the counters at the hashed positions and deletion decrements them, eliminating the delete‑problem but still retaining false positives.

Cuckoo Filter addresses the delete limitation by storing only short fingerprints of elements in a cuckoo‑hash‑style table. It uses two hash functions to map an element to two possible buckets; if both are full, one existing fingerprint is evicted to its alternative bucket, repeating until a free slot is found or the table is deemed full.

The cuckoo filter offers better space efficiency (up to ~40% savings over a Bloom filter at the same false‑positive rate) and supports deletions, but it can suffer from insertion loops when the table becomes too dense.

Cuckoo Hashing works with a one‑dimensional array and two hash functions. Insertion places an element in one of its two candidate slots; if both are occupied, a random victim is kicked out and re‑inserted into its alternate slot. The process may repeat, and if many kicks occur, the table is expanded.

Typical cuckoo‑hash improvements include using more hash functions (e.g., 3‑4) to increase the number of possible buckets, or adding multiple “slots” per bucket to raise occupancy without excessive kicks, achieving space utilizations of 85‑99% while maintaining high query speed.

For cuckoo filters, the fingerprint of an element (fp) is stored instead of the full key. The two bucket indices are computed as:

fp = fingerprint(x) p1 = hash(x) p2 = p1 ^ hash(fp) // XOR

Because the fingerprint is known, the alternate bucket can be derived from the current bucket via XOR, ensuring p1 ≠ p2 when hash(fp) ≠ 0 and avoiding self‑eviction loops.