Counting Bloom filter
A counting Bloom filter replaces each bit with a small integer counter. Inserting an item adds one to its k counters; deleting it subtracts one from each. A membership query asks whether all k counters are above zero. The extra space — typically four bits per slot rather than one — buys the one operation a plain Bloom filter cannot offer at all, because clearing an item’s bits would clear bits that other items depend on.
When it is the right choice
Whenever the set changes rather than only grows: a cache summary that has to forget evicted entries, a membership set with expiry, a router’s view of its neighbours. If nothing is ever removed, the extra space is wasted and a plain bit array is the right choice.
How it works
- Keep a small counter per slot instead of a bit, and add one to each of an item’s k slots when inserting it.
- Before deleting an item, run the ordinary membership test: every one of its k counters must be above zero.
- If the test passes, subtract one from each of those k counters. If it fails, refuse — the item provably was never inserted.
- A query still succeeds only when all k counters are above zero.
Worth noticing
- Deleting an item that really was inserted is safe, and the counters show why: a slot shared by three items drops from 3 to 2 and stays findable for the other two.
- Deleting something that was never inserted is the dangerous case, and the membership test only catches some of it. An item that is a false positive passes the test, so the delete is accepted — and it subtracts counters that belonged to real members, which is how a false negative gets in.
- Counters are small and can saturate. A four-bit counter stops at 15, and once it has saturated it can never safely be decremented again, because the structure no longer knows how many items are really there.
Cost
- Best
- O(1)
- Average
- O(k)
- Worst
- O(k)
- Space
- O(m) bits