Build a Bloom Filter and Watch ‘Probably Present’ Become a False Positive

A Bloom filter can say an item is definitely absent or probably present. It cannot prove membership. The easiest way to learn that distinction is to generate a false positive yourself.

import hashlib
class Bloom:
    def __init__(self, bits=128, hashes=3):
        self.bits=[0]*bits; self.k=hashes
    def positions(self, value):
        raw=value.encode()
        for i in range(self.k):
            yield int.from_bytes(hashlib.sha256(bytes([i])+raw).digest()[:8])%len(self.bits)
    def add(self, value):
        for p in self.positions(value): self.bits[p]=1
    def maybe(self, value):
        return all(self.bits[p] for p in self.positions(value))

Enter fullscreen mode Exit fullscreen mode

Insert deterministic values item-0000 through item-0099. Then query new values until maybe() returns true. Print the first false positive with bit count, hash count, inserted count, and query count.

Experiment table

Bits Hashes Inserted False positives / 10,000 128 3 100 measure 1,024 3 100 measure 1,024 7 100 measure

Use the same input sequence for each row. Test empty filters, repeated insertion, known members, and a deliberately undersized filter. Expected invariant: inserted items have no false negatives; absent items may be false positives.

Do not replace an authorization check or billing record with a Bloom filter. Use it as a cheap prefilter followed by an authoritative lookup when maybe() is true.

Python’s hash choices here are educational, not a production recommendation, and the measured rate is not universal. Which workload can tolerate an extra lookup but never a false negative?