Counting Bloom Filter

Same idea as a Bloom filter, but each slot is a small saturating counter instead of a single bit, so removing an item is safe.

How it works

A plain Bloom filter can never support remove() safely: clearing a bit might belong to several items that collided on it. A counting Bloom filter replaces each bit with a small counter (often 4 bits, so it saturates at 15). add() increments the k counters; remove() decrements them (only if the item currently tests as present).

The trade-off: k counters cost k× more memory than k bits (typically 4-8× total). This is the structure behind Summary Cache, used to let cooperating web caches share compact "what do you have" digests.

Interactive demo

Counters (m)48
Hash fns (k)4
Max counter value15
Peak counter0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new CountingBloomFilter(m, k, maxCount?)Allocate m saturating counters (default cap 15) with k hash functions.O(m) space
add(item): voidIncrement the k derived counters (capped at maxCount).O(k) time
remove(item): booleanDecrement the k counters if item currently tests present.O(k) time
has(item): booleanTrue if all k derived counters are non-zero.O(k) time

References

Original papers

Library implementations

Real-world use cases