Bloom Filter Bitwise

What Is a Bloom Filter?

I remember the first time I encountered a bloom filter while working on a caching layer for a high-traffic API. We had millions of keys in Redis, and every cache-miss query required a database lookup. A bloom filter sitting in front of the cache could tell us "this key definitely does not exist" using just a tiny fraction of memory. It changed how I thought about data structures entirely.

A bloom filter is a probabilistic data structure that answers one question: "Have I seen this element before?" It returns either "definitely not in the set" or "probably in the set." The "probably" part means false positives are possible, but false negatives are not — if the bloom filter says an element hasn't been inserted, it hasn't. This trade-off of perfect recall for memory efficiency is what makes bloom filters invaluable in large-scale systems.

I use Bloom filters in production for a caching layer that avoids expensive database lookups. The filter uses three hash functions and a 1-million-bit array. Setting and checking bits with OR and AND operations is so fast that the filter adds less than a microsecond per lookup.

The core of a bloom filter is a bit array of m bits and k independent hash functions. Every operation — insert and query — reduces to setting or testing bits using bitwise OR and AND operations.

How a Bloom Filter Works

Here is the step-by-step mental model I use. Initialize all m bits to 0. For each element you insert, run it through all k hash functions. Each hash function produces a position in the range [0, m-1]. Set the bit at each of those k positions to 1 using bitwise OR. To query an element, run the same k hash functions and check whether all k bits are set using bitwise AND. If any bit is 0, the element is definitely not in the set. If all bits are 1, the element is probably in the set.

Bitwise Implementation in Python

Here is a minimal but complete bloom filter implementation. Notice how the bit array operations rely entirely on bitwise OR (|) for setting bits and AND (&) for testing them.

class BloomFilter:
    def __init__(self, m, k):
        self.m = m          # bit array size
        self.k = k          # number of hash functions
        self.bits = 0       # bit array as Python integer
        self.seeds = [i * 0x9E3779B9 for i in range(k)]

    def _hash(self, item, seed):
        h = hash(item) ^ seed
        return (h & 0x7FFFFFFF) % self.m

    def add(self, item):
        for s in self.seeds:
            pos = self._hash(item, s)
            self.bits |= (1 << pos)     # bitwise OR — set bit

    def __contains__(self, item):
        for s in self.seeds:
            pos = self._hash(item, s)
            if (self.bits & (1 << pos)) == 0:  # bitwise AND — test bit
                return False        # definitely not in set
        return True                  # probably in set

False Positive Rate and Parameter Tuning

Every bloom filter has a mathematically predictable false positive rate. After inserting n elements into an m-bit array with k hash functions, the probability that a particular bit is still 0 is approximately e^(-kn/m). The false positive rate follows directly: (1 - e^(-kn/m))^k. In my own projects I almost always target m/n = 10 (10 bits per element) and k = 7 hash functions, which gives roughly a 1% false positive rate.

The optimal k — the number of hash functions that minimizes the false positive rate for a given m/n ratio — is (m/n) * ln(2). This is where the trade-off between computation (more hashes) and accuracy (more bits) balances out. I keep a cheat sheet in my notes:

Real-World Applications

Cassandra and Bigtable

When I was debugging a Cassandra performance issue, I discovered that every SSTable file has an associated bloom filter. Before Cassandra reads from an SSTable, it checks the bloom filter. If the filter says the row key doesn't exist in that SSTable, Cassandra skips it entirely — avoiding an unnecessary disk I/O operation. This is the most common real-world bloom filter pattern: a cheap bitwise check in front of an expensive lookup.

Medium's Article Recommendation

Medium uses bloom filters to avoid showing you articles you have already seen. When you open the homepage, they query the bloom filter for each candidate article. Articles that are "definitely not seen" — the filter says no — go straight to the recommendation pool. Articles that are "probably seen" get shuffled down or filtered out based on other signals.

Chromium's Safe Browsing

Chromium ships with a bloom filter representing known malicious URLs. Before every page load, the browser checks the URL against the local bloom filter. If the filter says "definitely safe," the browser proceeds without any server round trip. Only when the filter says "probably malicious" does Chromium make a network call to verify. This trades a small false positive rate (triggering occasional unnecessary network calls) for massive performance gains — the vast majority of URLs are never checked against Google's servers.

// Pseudocode for Chromium's safe browsing bloom filter check
function isUrlSafe(url) {
    let hash1 = hashFn1(url);
    let hash2 = hashFn2(url);
    let hash3 = hashFn3(url);
    let hash4 = hashFn4(url);

    // Bitwise AND test — if any bit is 0, URL is definitely safe
    let bits = safeBrowsingBloom.bits;
    if ((bits & (1n << BigInt(hash1))) === 0n) return true;
    if ((bits & (1n << BigInt(hash2))) === 0n) return true;
    if ((bits & (1n << BigInt(hash3))) === 0n) return true;
    if ((bits & (1n << BigInt(hash4))) === 0n) return true;

    return false; // probably malicious — ask the server
}

Variants and Extensions

Over the years I have used several bloom filter variants depending on the use case. The counting bloom filter replaces each bit with a 4-bit counter, enabling deletion. When a counter reaches zero, the corresponding bit is cleared. This is useful in caching scenarios where elements have TTLs and need to be removed after expiration. The scalable bloom filter — described by Almeida et al. — automatically grows a chain of bloom filters as more elements are inserted, maintaining a bounded false positive rate. I use this variant when I cannot predict the total number of elements in advance.

The blocked bloom filter divides the bit array into cache-line-sized blocks (typically 64 or 128 bytes) and assigns each hash function to a specific block. This improves CPU cache locality because all k bits for a given element are likely in the same cache line. In benchmark testing, blocked bloom filters can be 2-3x faster in high-throughput systems.