Bloom Filters

Probabilistic set membership structure. O(1) lookup, zero false negatives, non-zero false positive rate.

Guarantee: "not present" is always correct. "present" means "probably present."

Good fit: recommendation deduplication, cache pre-checks, initial pruning — anywhere a false positive costs less than the alternative (full lookup, network call, etc.).

Internals

Bit array of size m, k independent hash functions.

Insert: hash item with each of the k functions → set bits at the k resulting indices to 1.

Lookup: hash item → check all k bits. Any bit = 0 → definitely absent. All bits = 1 → probably present (those bits may have been set by collisions from other items).

No deletion: bits are shared across entries. Flipping a bit corrupts membership data for other items. Use Cuckoo filters if deletion is needed.

Key Formulas

m = ceil((n * log(p)) / log(1 / pow(2, log(2))))   # bits needed
k = round((m / n) * log(2))                          # optimal hash function count
p = pow(1 - exp(-k / (m / n)), k)                    # false positive probability
n = ceil(m / (-k / log(1 - exp(log(p) / k))))        # max items for given m, k, p

Calculator: hur.st/bloomfilter

Notes

• Hash functions don't need to be cryptographically secure — collisions are expected and accounted for; the modulo step is the actual bottleneck
• For very large n, RAM limits become the constraint before accuracy does — consider Cuckoo filters or partitioned variants