Bloom Filter

A bit array + k hash functions. Insert sets k bits; a query checks k bits. A 0 bit means definitely absent (no false negatives); all 1s means probably present (maybe a false positive).

Insert O(k) Query O(k) Space O(m) bits FPR ≈ (1−e^(−kn/m))^k No delete

bit = 0

bit = 1 (set)

inserting / probe hit

probe miss (a 0 found)

false positive

Controls

m (bits): 32 k (hashes): 3 speed:

Bit Array

m (bits)

k (hashes)

n (inserted)

bits set

fill ratio

est. FPR

What just happened

Insert a word to set its k bits, then query it or a different word. Try "Find a False Positive".

Complexity & False-Positive Rate

Operation	Time	Notes
Insert	O(k)	set k bits from k hashes
Query (might-contain)	O(k)	check k bits; early-exit on first 0
Delete	unsupported	shared bits → use counting Bloom filter
Space	O(m) bits	~10·n bits for 1% FPR
Optimal k	(m/n)·ln2	array half full of 1s
FPR p	(1−e^(−kn/m))^k	rises with n, falls with m
Sizing m	−n·ln p / (ln2)²	from target FPR p

Bloom Filter

Controls

Bit Array

What just happened

Complexity & False-Positive Rate

Operation Log