Counting Bloom Filter

A Bloom filter with a small counter per slot (max 15) instead of a bit. Insert increments k counters; Delete decrements them; a query needs all k counters > 0. The counter is what lets you delete — and saturating at the max keeps overflow safe.

Insert O(k) Delete O(k) Query O(k) Space ~4× Bloom FPR ≈ (1−e^(−kn/m))^k Saturate at 15

counter = 0

counter > 0 (set)

increment / probe hit

decrement (delete)

probe miss (a 0 found)

false positive / saturated (15)

Controls

m (slots): 24 k (hashes): 3 speed:

Counter Array (each slot holds 0..15)

m (slots)

k (hashes)

n (present)

slots set

mean counter

0.00

fill ratio

est. FPR

What just happened

Insert a word to increment its k counters. Insert two words that share a slot, delete one, and watch the shared counter drop but stay > 0 — that's why deletion is safe. Try "Force Overflow" to saturate a counter at 15.

Complexity, False-Positive Rate & Overflow

Operation	Action	Time	Notes
Insert	counter += 1	O(k)	saturate at 15 (never wrap)
Delete	counter −= 1	O(k)	clamp at 0; skip saturated
Query	all counters > 0?	O(k)	early-exit on first 0
Space	m × 4 bits	O(m·c)	~4× a Bloom filter
Optimal k	(m/n)·ln2	—	mean counter ≈ ln2 ≈ 0.69
FPR p	(1−e^(−kn/m))^k	—	same as Bloom; falls as you delete
Overflow (4-bit)	Pr[≥16] ≈ (ln2)¹⁶/16!	—	≈ 10⁻¹⁶ — essentially never

Counting Bloom Filter

Controls

Counter Array (each slot holds 0..15)

What just happened

Complexity, False-Positive Rate & Overflow

Operation Log