Bloom Filters: Size, False Positives and Safe Use

Bloom filters: skip work when the answer is definitely no

A Bloom filter is a compact membership structure. Under its normal insertion-only assumptions, a negative result means an item was not inserted; a positive result means it may have been. The structure trades false positives for memory savings. It does not store the original members or enumerate them.

The standard analysis models a bit array and hash probes. Broder and Mitzenmacher's survey explains the construction and its applications. Network Applications of Bloom Filters.

Follow one insertion

Start with an array of zero bits. Hash an item to several bit positions and set them to one. A lookup checks those same positions. If any is zero, this filter has not recorded the item. If all are one, the item or other colliding items may have set them.

Bits are shared. Clearing a bit to “delete” one item can make another inserted item appear absent. Use a data structure designed for deletion, or rebuild the filter from the authoritative set. Concurrent writers must also update bits without losing each other's changes.

Work out the memory budget

For expected insertions n and desired false-positive probability p, the usual approximation is:

m = -n × ln(p) / (ln(2)²)    bits
k = (m / n) × ln(2)         hash probes, rounded to an integer
p ≈ (1 - exp(-k × n / m))^k

With one million items and p = 0.01, the budget is approximately 9.59 million bits, 1.20 MB in decimal units, or 1.14 MiB. Seven probes are a reasonable rounded choice. This is the bit-array payload; allocator and object metadata add overhead. A Python list of booleans is not a packed bit array and will not meet that memory estimate.

If that same array receives two million distinct items, the approximation gives a false-positive probability of about 15.7%. Capacity is a quality limit even when the structure continues accepting insertions.

A runnable packed-bit demonstration

This educational Python implementation uses a byte array and separately prefixed SHA-256 hashes. It favors clarity over maximum throughput and is intended for single-threaded use.

import hashlib
import math

class BloomFilter:
    def __init__(self, capacity, error_rate):
        if capacity <= 0 or not 0 < error_rate < 1:
            raise ValueError("positive capacity and 0 < error_rate < 1 required")
        self.m = math.ceil(-capacity * math.log(error_rate) / math.log(2)**2)
        self.k = max(1, round(self.m / capacity * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)

    def positions(self, item):
        payload = item.encode("utf-8")
        for probe in range(self.k):
            digest = hashlib.sha256(probe.to_bytes(4, "big") + payload).digest()
            yield int.from_bytes(digest, "big") % self.m

    def add(self, item):
        for position in self.positions(item):
            self.bits[position // 8] |= 1 << (position % 8)

    def might_contain(self, item):
        return all(
            self.bits[position // 8] & (1 << (position % 8))
            for position in self.positions(item)
        )

bloom = BloomFilter(10_000, 0.01)
bloom.add("alice")
assert bloom.might_contain("alice")
print(len(bloom.bits), "bytes in the bit array")

This example omits persistence, multi-process synchronization, compatibility versioning, and adversarial-load protection. Use a maintained implementation when those are requirements. Redis documents a supported Bloom filter API and capacity configuration. Redis Bloom filter documentation.

Savings depend on the queries

Suppose 100,000 lookups are 90% for absent keys, and the filter has a 1% false-positive rate for absent keys. Approximately 900 absent lookups still reach the database, along with all 10,000 present lookups. That is about 10,900 database checks rather than 100,000, before other costs. If most queries are for present keys, the same filter saves much less.

The false-positive rate applies to absent items, not to all positive answers. In this example, approximately 900 of 10,900 positives are false—about 8.3%. This distinction matters when interpreting measurements.

Keep the authoritative decision authoritative

For username registration, a negative can avoid a preliminary availability lookup, but a unique database constraint must still arbitrate concurrent registrations. For a crawler, treating every positive as “already visited” can omit unseen pages; consult the visited store if coverage matters.

For a security blocklist, “not in this filter” does not mean “safe.” The filter may represent an incomplete or outdated known-bad list. Even the data structure's no-false-negative property requires that relevant items were inserted correctly and the query uses the same encoding and hash configuration.

If a growing design uses several filters, their error probabilities combine. A conservative bound is their sum, so assign a total budget—for example p/2, p/4, p/8, and so on—rather than giving every layer the full target rate. Monitor actual insertions, bit occupancy, and downstream positive confirmations. A useful check inserts a known set, verifies every member remains positive, and measures false positives on a disjoint sample; report sample size and configuration rather than a universal performance claim.