Bloom filters in Python: a tiny index that sometimes says maybe

A membership check sounds modest: has this identifier appeared before? A Python set gives an exact answer and is usually the sensible starting point. Trouble arrives when the collection is large, memory is tight, or the real answer lives in a slower database or service. Keeping a full local copy may cost more than the question deserves.

A Bloom filter takes a different bargain. It represents a set in a compact bit array and allows false positives in exchange for lower memory use.^[1] A negative answer is definite, while a positive answer means only “possibly present” and may need confirmation from the original store.^[2] That wording matters. A Bloom filter is a bouncer with a very small clipboard, not a court of final appeal.

The idea in bits

Start with an array of m zero bits and choose k hash probes. Adding an item hashes it to k positions and sets those bits to one. Looking up an item checks the same positions. One zero proves that the item was never added. If every selected bit is one, the item may be present, but unrelated items might have set the same pattern.

The expected false-positive rate depends on the number of stored items, the bit count and the number of probes. For a requested rate p and expected capacity n, a common sizing choice is m = ceil(-n ln(p) / ln(2)^2), followed by k = round((m / n) ln(2)). The survey by Broder and Mitzenmacher derives the optimum near (m / n) ln(2) probes and explains the resulting space and error trade-off.^[1]

More probes are not automatically better. Each one costs CPU time, and setting too many bits eventually makes positive answers commonplace. The capacity and target error rate are part of the data structure, not decorative constructor arguments.

A complete Python comparison

The program below builds an exact set and a Bloom filter for the same 200,000 strings. It verifies that the Bloom filter misses none of the inserted items, tests 100,000 absent strings, estimates each index’s memory, and times the same mixed workload seven times.

The implementation derives two 64-bit values from a 16-byte BLAKE2b digest, then uses double hashing to generate the bit positions. Python’s hashlib documentation specifies the configurable BLAKE2b digest size used here.^[3] This is a teaching implementation rather than a replacement for a mature library: it is single-process, has no serialisation format, and does not defend against concurrent mutation.

from __future__ import annotations
import hashlib
import math
import platform
import random
import statistics
import sys
import timeit
ITEM_COUNT = 200_000
ABSENT_QUERY_COUNT = 100_000
TARGET_FALSE_POSITIVE_RATE = 0.01
REPEATS = 7
SEED = 20260814
class BloomFilter:
    def __init__(self, capacity: int, false_positive_rate: float) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        if not 0 < false_positive_rate < 1:
            raise ValueError("false_positive_rate must be between 0 and 1")
        bits = math.ceil(
            -capacity * math.log(false_positive_rate) / math.log(2) ** 2
        )
        self.bit_count = bits
        self.hash_count = max(1, round(bits / capacity * math.log(2)))
        self.bits = bytearray((bits + 7) // 8)
    def _positions(self, value: str):
        digest = hashlib.blake2b(value.encode(), digest_size=16).digest()
        first = int.from_bytes(digest[:8], "little")
        second = int.from_bytes(digest[8:], "little") or 1
        for index in range(self.hash_count):
            yield (first + index * second) % self.bit_count
    def add(self, value: str) -> None:
        for position in self._positions(value):
            self.bits[position >> 3] |= 1 << (position & 7)
    def __contains__(self, value: str) -> bool:
        return all(
            self.bits[position >> 3] & (1 << (position & 7))
            for position in self._positions(value)
        )
def median_seconds(statement, *, repeat: int = REPEATS) -> float:
    return statistics.median(timeit.repeat(statement, number=1, repeat=repeat))
def main() -> None:
    rng = random.Random(SEED)
    values = [f"item-{number:016x}" for number in range(ITEM_COUNT)]
    exact = set(values)
    bloom = BloomFilter(ITEM_COUNT, TARGET_FALSE_POSITIVE_RATE)
    for value in values:
        bloom.add(value)
    absent = [
        f"missing-{rng.getrandbits(64):016x}" for _ in range(ABSENT_QUERY_COUNT)
    ]
    mixed = values[::20] + absent
    rng.shuffle(mixed)
    missing_inserted = sum(value not in bloom for value in values)
    false_positives = sum(value in bloom for value in absent)
    exact_positive_count = sum(value in exact for value in mixed)
    bloom_positive_count = sum(value in bloom for value in mixed)
    exact_seconds = median_seconds(
        lambda: sum(value in exact for value in mixed)
    )
    bloom_seconds = median_seconds(
        lambda: sum(value in bloom for value in mixed)
    )
    exact_bytes = sys.getsizeof(exact) + sum(sys.getsizeof(value) for value in exact)
    bloom_bytes = sys.getsizeof(bloom) + sys.getsizeof(bloom.bits)
    observed_rate = false_positives / len(absent)
    query_ratio = bloom_seconds / exact_seconds
    memory_ratio = exact_bytes / bloom_bytes
    print(f"Python: {platform.python_implementation()} {platform.python_version()}")
    print(f"Platform: {platform.platform()}")
    print(f"Seed: {SEED}")
    print(f"Stored items: {ITEM_COUNT:,}")
    print(f"Mixed queries: {len(mixed):,} ({len(values[::20]):,} present, {len(absent):,} absent)")
    print(f"Target false-positive rate: {TARGET_FALSE_POSITIVE_RATE:.2%}")
    print(f"Bloom bits: {bloom.bit_count:,}")
    print(f"Hash probes per Bloom query: {bloom.hash_count}")
    print(f"Inserted items missed by Bloom filter: {missing_inserted}")
    print(f"Observed false positives: {false_positives:,} / {len(absent):,} ({observed_rate:.3%})")
    print(f"Exact-set positives: {exact_positive_count:,}")
    print(f"Bloom-filter positives: {bloom_positive_count:,}")
    print(f"Exact-set estimated index size: {exact_bytes:,} bytes")
    print(f"Bloom-filter estimated index size: {bloom_bytes:,} bytes")
    print(f"Estimated memory ratio: {memory_ratio:.1f}x smaller")
    print(f"Exact-set query median: {exact_seconds:.6f} s")
    print(f"Bloom-filter query median: {bloom_seconds:.6f} s")
    print(f"Bloom/set query-time ratio: {query_ratio:.1f}x")
    assert missing_inserted == 0
    assert exact_positive_count == len(values[::20])
    assert bloom_positive_count == exact_positive_count + false_positives
if __name__ == "__main__":
    main()

The program prints the environment, fixed random seed, workload and measured medians:

Python: CPython 3.13.5
Platform: Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41
Seed: 20260814
Stored items: 200,000
Mixed queries: 110,000 (10,000 present, 100,000 absent)
Target false-positive rate: 1.00%
Bloom bits: 1,917,012
Hash probes per Bloom query: 7
Inserted items missed by Bloom filter: 0
Observed false positives: 1,033 / 100,000 (1.033%)
Exact-set positives: 10,000
Bloom-filter positives: 11,033
Exact-set estimated index size: 20,788,824 bytes
Bloom-filter estimated index size: 239,732 bytes
Estimated memory ratio: 86.7x smaller
Exact-set query median: 0.044918 s
Bloom-filter query median: 1.039933 s
Bloom/set query-time ratio: 23.2x

What the numbers mean

On this run, the estimated exact-set index occupied 20,788,824 bytes. The Bloom filter occupied 239,732 bytes, about 86.7 times less. It missed none of the inserted values and returned 1,033 false positives among 100,000 absent queries, an observed rate of 1.033% against the requested 1%.

The smaller structure was not faster. The exact set completed the mixed workload in a median 0.044918 seconds, while the pure-Python Bloom filter took 1.039933 seconds. That makes the Bloom lookup about 23.2 times slower here. Seven bit probes, digest calculation and Python-level iteration have real costs; the set implementation benefits from highly optimised native code.

Those timings do not contradict the mathematical benefit. A Bloom query performs k probes, so its work stays tied to the configured error rate rather than growing with the stored population. Its memory is the bit array, roughly m bits. The exact set also offers average constant-time membership, but it retains the keys and a hash table. In this particular program, Bloom filtering optimises memory and accepts both slower local queries and probabilistic answers.

Absolute times will change with the processor, Python version, inputs and hash implementation. The test ran in one process on CPython 3.13.5, 64-bit ARM Linux 6.12.47, with short ASCII strings. The memory estimate uses sys.getsizeof for the set, its strings, the Bloom object and its byte array. It does not measure allocator fragmentation, interpreter-wide state or a production library’s metadata.

Where the optimisation pays

A Bloom filter becomes more interesting in front of a backing check that is slower than the filter. If it rejects 98 or 99 out of 100 absent requests locally, those requests never need a disk lookup, database query or network call. Database and network applications are established uses of Bloom filters.^[1] Positive results still go to the exact store when correctness is required. The small local index then saves expensive operations rather than trying to beat a Python set in a sprint it is unlikely to win.

The technique is a poor fit when every answer must be exact and the full set already fits comfortably in memory. It is also awkward when items must be removed: clearing a shared bit could make another stored item disappear, so deletions require a different design such as a counting Bloom filter.^[1] Underestimating capacity raises the false-positive rate, and a tiny collection rarely repays the extra machinery.

Use the structure when memory or avoided backing-store calls matter more than exact local membership. Keep the set when certainty, simple code and low in-process latency matter most. The useful optimisation is choosing which resource to spend, not declaring one data structure the winner everywhere.

Sources

1. Network Applications of Bloom Filters: A Survey
2. Guava BloomFilter API
3. Python hashlib documentation