Implementing a Bloom Filter for Space-Efficient Membership Tests

A Bloom filter is a probabilistic data structure for checking whether an item may belong to a set. It uses a compact bit array and several hash functions, so it can handle large collections with very little memory. The trade-off is important: it can report a false positive, but it never reports a false negative when implemented correctly.

This makes Bloom filters useful for web services, databases, caches, distributed systems, and duplicate detection. A request can be rejected or routed quickly when the filter says an item is definitely absent, while a positive result triggers a more authoritative lookup. This guide develops a Python implementation, explains the mathematics behind its parameters, and covers practical design decisions for Australian applications.

Why Membership Tests Need Compact Data Structures

A standard Python set provides accurate membership tests with average-case constant-time lookup. Its memory usage, however, can become substantial because every element carries object, table, and hashing overhead. A set containing millions of strings may consume hundreds of megabytes, particularly when the strings themselves are long.

A Bloom filter stores no original values. It records only whether certain bit positions have been activated by hash functions. For a news recommendation service in Melbourne or an online retailer serving Sydney customers, this can provide a fast first check before reading a larger database or cache. The filter is especially useful when most lookup requests are for values that do not exist.

The data structure is also a good example of a broader algorithmic idea: trading a small, measurable accuracy risk for lower memory consumption. Related explanations of computational techniques are collected in algorithm tutorials, including the complexity reasoning needed to evaluate such trade-offs.

Bit Arrays, Hashes, And Probabilistic Results

A Bloom filter begins with an array of m bits, all set to zero. To insert an item, the implementation computes k independent-looking positions and changes those bits to one. To query the item, it computes the same positions. If at least one position is zero, the item was definitely never inserted. If every position is one, the item may have been inserted.

False positives occur because different values can set the same positions. Suppose "alice@example.com" and "bob@example.com" activate overlapping bits. A later query for "carol@example.com" might find all of its positions set by other values and incorrectly return “possibly present”. This is a limitation of the representation, not necessarily a programming error.

False negatives should never occur if insertion and lookup use identical normalisation, encoding, hash functions, and parameter values. For example, treating "Product-42" and "product-42" as different strings during insertion but as equivalent during lookup creates an application-level inconsistency. Decide whether values are case-sensitive before they enter the filter.

Selecting Hash Functions And Parameters

A common implementation uses double hashing. Two base hashes, h1 and h2, generate each position with:

position(i) = (h1(item) + i × h2(item)) mod m

This avoids storing k separate hash algorithms while producing a useful sequence of positions. Cryptographic hashes from Python’s hashlib module are convenient because they are stable across processes, unlike Python’s built-in hash() function, which is intentionally randomised between interpreter runs.

For n expected items and a target false-positive probability p, the standard sizing formulas are:

m = -n × ln(p) / (ln(2)²)
k = (m / n) × ln(2)

Here, m is the number of bits and k is the number of hash positions per item. A target probability of 0.01 means approximately one false positive in every one hundred negative queries under the model’s assumptions. Rounding m upward and selecting an integer k near the calculated value is sensible.

Memory usage is approximately m / 8 bytes, excluding object overhead. A filter sized for ten million values with a one per cent target false-positive rate needs roughly 12 MB of bit storage. The real rate can differ if the item count is underestimated, inputs are highly structured, or the hash distribution is poor.

Building A Bloom Filter In Python

The following class uses a bytearray to store the bit array. Each bit position is converted into a byte index and a bit mask. The second digest is forced to be odd, which helps the generated step move through the bit array more effectively when the modulus has convenient factors.

import hashlib
import math


class BloomFilter:
    def __init__(self, expected_items, false_positive_rate=0.01):
        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")

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

    def _positions(self, item):
        value = str(item).encode("utf-8")
        digest = hashlib.blake2b(value, digest_size=16).digest()
        first = int.from_bytes(digest[:8], "big")
        second = int.from_bytes(digest[8:], "big") | 1

        for index in range(self.hash_count):
            yield (first + index * second) % self.size

    def add(self, item):
        for position in self._positions(item):
            byte_index, bit_index = divmod(position, 8)
            self.data[byte_index] |= 1 << bit_index

    def __contains__(self, item):
        for position in self._positions(item):
            byte_index, bit_index = divmod(position, 8)
            if not (self.data[byte_index] & (1 << bit_index)):
                return False
        return True

Usage is straightforward:

blocked = BloomFilter(expected_items=1_000_000, false_positive_rate=0.005)
blocked.add("device-123")

if "device-123" in blocked:
    print("Possibly blocked")

The result means “possibly present”, even though the Python membership syntax looks like an ordinary set lookup. A production API should document this distinction clearly. The filter should usually be followed by an exact check before deleting data, denying an account, or claiming that a record exists.

Understanding Accuracy, Capacity, And Lifecycles

The false-positive formula for a Bloom filter with m bits, k hash functions, and n inserted items is approximately:

p ≈ (1 - e^(-kn/m))^k

As more items are inserted, more bits become one and the false-positive rate rises. A filter designed for one million entries should not quietly receive five million entries. Capacity is therefore a lifecycle concern, not simply a constructor argument.

Bloom filters do not support ordinary deletion. Clearing the bits for one item could also remove evidence belonging to other items. If deletion is required, use a counting Bloom filter with small counters, a backing set, or rebuild the filter periodically from the source of truth. A scalable design can maintain several generations, replacing an old filter when it reaches a planned load factor.

Persistence also needs care. Save the bit array together with size, hash_count, encoding rules, and the hash algorithm identifier. A filter restored with a different parameter set will produce incorrect results. In a distributed service, all workers must use the same serialisation format and configuration.

Testing And Integrating The Structure

Tests should verify the guarantee that every inserted item is found. Generate a known collection, add each value, and assert membership for all of them. Then generate a separate collection of values that were not inserted and measure the proportion reported as present. This empirical result will vary with the sample, but a large test should be reasonably close to the configured target.

Benchmark both memory and latency. Compare the filter with a Python set, measuring insertion time, query time, resident memory, and the behaviour after the expected capacity is exceeded. Also test normalisation rules such as whitespace trimming, Unicode handling, and lower-casing. These details often matter more than the hash function in an application built around user-entered data.

A Bloom filter can precede a database query, but it should not replace a database index. The same principle appears in this SQL indexing guide, where an efficient preliminary decision still works alongside an exact data store. In an Australian online marketplace, for example, a filter might screen product IDs before a PostgreSQL lookup, while the database remains responsible for authoritative results.

Practical Uses In Australian Systems

A filter can support URL deduplication in a crawler, suppress repeated event identifiers in a data pipeline, or avoid cache misses for keys that have never existed. Australian services handling tap-and-go shopping habits, parcel tracking, or large daily batches of customer activity can use the technique to reduce unnecessary reads from slower storage. The likely workload should determine whether the probabilistic result is useful.

Privacy requires particular attention. A Bloom filter cannot reconstruct the original values easily, but it still leaks information through membership queries, especially when an attacker can test many guesses. A service handling personal information should consider the Australian Privacy Act and the Australian Privacy Principles when deciding whether identifiers, email addresses, health-related values, or device tokens belong in a remotely accessible filter. Hashing is not a substitute for access control or appropriate retention rules.

Geography can influence architecture too. A system split between Sydney, Melbourne, and Brisbane may replicate filters to reduce lookup latency, but each replica needs a clear update policy. A stale filter usually causes extra exact lookups rather than incorrect final answers, provided the backing store is authoritative. For high-volume systems, versioned snapshots and atomic replacement are safer than mutating a shared filter while other processes read it.

For a practical engineering checklist, keep these decisions explicit:

• Estimate the maximum number of inserted values rather than the current count.
• Choose a false-positive rate based on the cost of an unnecessary exact lookup.
• Use stable hashing and document the encoding and normalisation rules.
• Keep an authoritative set, database, or service behind the probabilistic check.
• Monitor occupancy and measured false-positive rates in production.
• Rebuild, rotate, or replace the filter when its planned capacity is reached.

Comparing Alternatives And Avoiding Misuse

A Bloom filter is suitable when false positives are acceptable and deletions are uncommon. A hash set is preferable when exact answers, iteration, or removal are required and memory is available. A sorted array can offer compact storage with binary search when updates are infrequent. A Cuckoo filter may be a better choice when deletion and membership fingerprints are important.

The data structure also fits naturally into layered algorithms. For example, a service can check a Bloom filter, query a local cache after a possible hit, and finally consult a database. This pattern reduces expensive operations while preserving correctness. It resembles the discipline used in the container problem walkthrough: first identify the property that permits work to be skipped, then prove that the shortcut does not remove valid answers.

Used carefully, a Bloom filter turns memory into a controlled probability of extra work. Its value comes from clear capacity planning, stable hashing, measured behaviour, and a reliable exact data source behind it. That combination makes space-efficient membership tests practical rather than merely theoretical.