bloom-filter

A Bloom filter in pure Python: a space-efficient probabilistic set that answers "have I seen this before?" — and whose error rate is a checkable prediction, not a promise.

A Bloom filter gives one of two answers:

• "definitely not in the set" — always correct. There are no false negatives.
• "possibly in the set" — may be wrong. False positives are allowed by design, and their probability is what the mathematics predicts.

The whole point of this repo is that the false-positive rate is not a vibe. It is the number (1 - e^(-k*n/m))^k, and the test suite measures the real rate over 100 000 queries and checks it against exactly that formula.

Pure standard library, no dependencies. Copy bloom.py in, or import it.

from bloom import BloomFilter

bf = BloomFilter(capacity=10_000, error_rate=0.01)
bf.add("hello")
bf.add(b"raw bytes work too")

"hello" in bf          # True  (definitely inserted)
"never added" in bf    # almost always False; sometimes a false positive

bf.m                              # number of bits
bf.k                              # number of hash functions
bf.expected_false_positive_rate() # predicted FP rate at current fill

Given a capacity n (how many items you plan to store) and a target false-positive rate p, the constructor derives the two standard optimal parameters:

m = ceil(-n * ln(p) / (ln 2)^2)     # number of bits
k = round((m / n) * ln 2)           # number of hash functions (>= 1)

Bits are packed into a bytearray, one bit per position.

To insert or query an item, we need k independent bit positions. Instead of computing k separate hashes, we take one SHA-256 digest, split it into two 64-bit halves h1 and h2, and use double hashing:

position(i) = (h1 + i * h2) mod m,   for i = 0 .. k-1

This is the Kirsch–Mitzenmacher construction: two hash values are enough to generate k effectively-independent positions without raising the error rate.

add sets those k bits. contains returns True only if all k bits are set. Because an inserted item's bits are never unset, an inserted item is always found — that is the no-false-negatives guarantee. A non-inserted item is a false positive exactly when all k of its bits happen to already be set by other items.

After inserting n items into m bits with k hashes, the probability that a given never-inserted item collides on all k bits is:

FP = (1 - e^(-k*n/m))^k

test_bloom.py does not trust this — it verifies it:

1. Build a filter for a target p, insert n = capacity random items.
2. Query M = 100 000 items drawn from a disjoint namespace (asserted disjoint), so none were inserted. Count how many the filter wrongly reports as present.
3. Check that the measured rate lands within ±25% (relative) of the theoretical (1 - e^(-k*n/m))^k, and is grossly near the target p.

The tolerance band is not arbitrary. With M = 100 000, the sampling standard deviation of the measured rate is sqrt(p*(1-p)/M) — roughly 3% relative at p = 0.01. A ±25% band is many standard deviations wide, and because every test seeds its own random.Random, runs are fully reproducible and the test does not flake.

Measured vs. theoretical on the committed seeds:

Be honest about the boundaries:

• It is probabilistic. False positives happen by design — a "yes" means "probably", never "certainly".
• No false negatives, ever. If it says "no", the item was truly never added. This is a hard guarantee (tested up to 50 000 items).
• No deletion. This is a standard Bloom filter. You cannot remove an item (clearing bits would create false negatives for other items). If you need deletion, you want a counting Bloom filter, which this is not.
• Fixed size after construction. m and k are fixed once you choose capacity and error_rate. Inserting far more than capacity items degrades the false-positive rate above the target p; the filter does not grow.
• Not cryptographic. SHA-256 is used purely as a fast, well-distributed hash for bit placement. This is not a security primitive, does not resist an adversary crafting collisions, and stores no items — you cannot recover what was inserted from the bit array.
• Uses hashlib. Hashing is a tool here, not the thing being reimplemented. Only the standard library is used.

python -m unittest -v

All 10 tests should pass in a couple of seconds. CI runs the same command on Python 3.12 (see .github/workflows/check.yml).

MIT — see LICENSE.