Counting Bloom Filter (Fan, Cao, Almeida, Broder 2000)

Basic Bloom can't DELETE. Counting Bloom replaces each 1-bit slot with a small counter (typically 4 bits, max value 15).

Semantics

ADD(x):     for p in positions(x): counter[p] = min(counter[p] + 1, MAX)
REMOVE(x):  if any counter[p] == 0 -> WAS_ABSENT
            else: for p: counter[p] = max(counter[p] - 1, 0)
CHECK(x):   MAYBE if all counter[p] > 0 else NO

Saturation: the tradeoff that bites

4-bit counters can represent counts 0..15. What if 16 items collide on the same slot? You must saturate (clamp at 15) — wrapping around to 0 would create false negatives later.

Worse: once a counter saturates, you can never accurately decrement it again. Decrementing a saturated slot loses information; the safe choice is to leave saturated counters alone (some implementations log a warning and never touch them again). Size counters wide enough that saturation is extremely unlikely (a few sigmas past expected max collisions per slot).

Memory cost

4-bit counters use 4x the memory of a basic Bloom for the same m, k. If you need delete and can afford the memory, Counting Bloom is straightforward. If you need delete AND want better space efficiency, the Cuckoo filter (next variant) is usually better.

Multiplicity bonus

The minimum counter across an item's k positions is a (lower-bound) estimate of how many times that item was added — a free side benefit not present in basic Bloom. This is the API's COUNT command.