Building Bloom filters for space-efficient membership tests

A Bloom filter is a probabilistic set-membership data structure built around a compact bit array. Instead of retaining complete keys, it records the effects of several hash functions. A query can establish that an element is absent, or report that it might be present with a controlled probability of error. This makes the filter useful for space-efficient membership tests when exact storage is costly but occasional false positives can be tolerated.

The error is directional: a standard Bloom filter has no false negatives for inserted keys, while false positives are possible. This suits cache prefilters, duplicate detection and rapid rejection before an authoritative lookup. It does not suit access control, financial balances or any decision requiring certainty, because a reported match still needs confirmation from the real set.

Why approximate membership is useful

An exact Python set stores every key and answers membership with certainty, but its memory overhead can dominate for large collections of URLs, identifiers or document fingerprints. A Bloom filter stores only bits. Adding an item sets several hashed bit positions; a lookup reports absent when any required bit is zero and reports maybe when all are set. Other keys may have set those bits, creating a false positive.

The filter is most effective as an early-rejection layer. A web service can check it first, skip an expensive database or network request when the answer is definitely no, and consult the exact index when the filter says maybe. This pattern reduces latency and traffic without pretending that the compressed structure replaces the source of truth.

The distinction is easier to appreciate alongside a deliberately inefficient teaching algorithm. The stooge sort guide explores repeated sorting and division, whereas a Bloom filter deliberately introduces approximation to avoid keeping complete values. Both show why choosing the right algorithm depends on the resource being optimised.

Choosing the bit array and hash count

Let n be the expected number of unique insertions, m the number of bits and p the desired false-positive probability. The standard sizing equation is m = ceil(-n ln(p) / (ln 2)^2). Once m is known, a good hash count is k = round((m/n) ln 2). Space is O(m) bits, while each insertion or membership test touches only O(k) positions.

For example, 100,000 identifiers with a one-percent target require about 958,506 bits, or roughly 117 KiB, and seven hash positions. That is much smaller than storing 100,000 strings and their Python object overhead. Settings for a growing workload should include headroom because an overfilled filter quickly loses its intended accuracy.

Hash functions should distribute keys across the whole array and remain stable for the filter’s lifetime. Two 64-bit values from a cryptographic digest can be combined through double hashing to obtain the k positions. Unlike the reverse-delete method, which removes graph edges while preserving a minimum spanning tree, a Bloom filter has no ordinary deletion operation: clearing a shared bit could make another stored key appear absent.

Implementing a Bloom filter in Python

A compact implementation can use a bytearray for the packed bits and derive each position with double hashing. The following class follows the sizing equation, keeps a fixed salt and exposes a deliberately cautious method name: might_contain.

import hashlib
import math


class BloomFilter:
    def __init__(
        self,
        expected_items,
        false_positive_rate=0.01,
        salt=b"hello-ml-bloom-v1",
    ):
        if expected_items <= 0:
            raise ValueError("expected_items must be positive")
        if not 0 < false_positive_rate < 1:
            raise ValueError("false_positive_rate must be between 0 and 1")

        self.bit_count = math.ceil(
            -expected_items
            * math.log(false_positive_rate)
            / (math.log(2) ** 2)
        )
        self.hash_count = max(
            1, round((self.bit_count / expected_items) * math.log(2))
        )
        self.bits = bytearray((self.bit_count + 7) // 8)
        self.salt = salt

    def _positions(self, item):
        if not isinstance(item, (str, bytes)):
            raise TypeError("item must be a string or bytes")

        data = item.encode("utf-8") if isinstance(item, str) else item
        digest = hashlib.blake2b(data + self.salt, digest_size=16).digest()
        first = int.from_bytes(digest[:8], "little")
        second = int.from_bytes(digest[8:], "little") or 1

        return [
            (first + index * second) % self.bit_count
            for index in range(self.hash_count)
        ]

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

    def might_contain(self, item):
        for position in self._positions(item):
            if not (self.bits[position // 8] & (1 << (position % 8))):
                return False
        return True

Create the filter with an expected workload, add canonical key representations, then query it. If might_contain returns False, the key is absent under the standard assumptions. If it returns True, check the authoritative set before treating the item as a match. For example, a URL filter should first normalise host names consistently, or logically identical spellings can be stored as unrelated keys.

Persisting a filter requires more than writing the bit array. Keep the bit count, hash count, salt and encoding rules together; changing any of them invalidates existing positions. In a concurrent service, protect updates with a lock or use immutable snapshots. Hashing a long key also costs time proportional to its length, so very large values are often better reduced to a stable fingerprint before insertion.

Tuning accuracy and query cost

The approximate false-positive probability is (1 - e^(-kn/m))^k. This expression is valuable for comparing configurations, but it is not a guarantee for every key set. Hash quality, clustering and an unexpectedly high insertion count can make observed errors differ from the model.

Using more hash positions lowers false positives only up to the optimum for the chosen array size. Beyond that point, each query does more work for little gain. A very small k is faster but produces more collisions; a larger k improves separation while increasing CPU and latency. Benchmark the complete path, including the exact lookup that follows a positive result.

Parameter choices should be tested against representative data rather than accepted from a formula alone. The same evidence-driven habit used for gradient boosting regression is useful here: compare several configurations, record the false-positive rate and measure memory, throughput and tail latency on the hardware that will run the service.

Applying the filter in Australian systems

In an online marketplace serving Sydney and Melbourne, repeated catalogue requests can consume database capacity even when most product identifiers are unknown. A filter in front of the product index can reject those requests cheaply. If it reports maybe, the application still queries the catalogue, so existing accuracy and ranking behaviour remain unchanged.

Grocery search is another realistic case. Coles and Woolworths catalogues contain many closely related products, abbreviations and spelling variations, so a typo-tolerant search layer can use a Bloom filter to identify possible matches before consulting a dictionary. The filter reduces lookups; it does not decide that two similar names refer to the same item.

Filters also suit API gateways, log pipelines, URL blocklists and cache warming. Australian cloud regions around Sydney and Melbourne make data placement explicit for organisations with local residency requirements, and keeping the filter beside the protected dataset can reduce cross-region traffic. A compact filter is useful here because its storage depends on the number of bits rather than the full size of stored keys.

Developers can compare different implementations and hash functions at Python community meetups from Brisbane to Perth, then reproduce those benchmarks in production-like containers. A practical test set should contain expected members, known non-members and adversarial or clustered inputs, giving a clearer picture than checking only a handful of successful inserts.

Practical guidance for dependable use

Reliable adoption comes from treating the filter as an optimisation with explicit assumptions. Estimate the expected number of unique keys, understand the cost of a false positive and preserve the configuration that defines the bit positions.

• Estimate expected unique insertions before sizing the filter and reserve capacity for expected growth.
• Choose the target false-positive rate according to the consequences of an incorrect match.
• Use stable, well-distributed hashes and retain the same salt and encoding rules.
• Benchmark insertion, lookup and exact-verification paths at representative scale.
• Treat every possible match as a candidate and confirm it against authoritative data.
• Rebuild filters for changing datasets instead of attempting to delete individual entries.

For changing datasets, rebuilding a filter is usually safer than attempting deletion. Version filters when a cached process may still hold an older bit array, and expose metrics for rejected queries, candidate lookups and observed false positives. With those controls, a Bloom filter can provide substantial space savings while preserving correctness in the authoritative system.