Bloom Filters and Probabilistic Data Structures

Probabilistic data structures trade tiny accuracy for huge space savings. They answer “probably” instead of “definitely.”

Bloom Filters

What is a Bloom Filter?

A space-efficient data structure that tests set membership. It can say:

• “Definitely not in the set” (100% accurate)
• “Probably in the set” (some false positive rate)

How It Works

Initialize: Bit array of m bits, all 0
            k hash functions

Insert "apple":
  h1("apple") → position 3    → set bit 3 = 1
  h2("apple") → position 7    → set bit 7 = 1
  h3("apple") → position 12   → set bit 12 = 1

Check "apple":
  h1("apple") → position 3    → bit is 1 ✓
  h2("apple") → position 7    → bit is 1 ✓
  h3("apple") → position 12   → bit is 1 ✓
  → "Probably in set"

Check "banana":
  h1("banana") → position 3   → bit is 1 ✓
  h2("banana") → position 5   → bit is 0 ✗
  → "Definitely NOT in set"

Performance

False Positive Rate

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

Where:
  n = number of items inserted
  m = number of bits
  k = number of hash functions

Optimal k: k = (m/n) * ln(2)

Implementation

import math
import hashlib

class BloomFilter:
    def __init__(self, n, fp_rate=0.01):
        self.m = int(-n * math.log(fp_rate) / (math.log(2) ** 2))
        self.k = int((self.m / n) * math.log(2))
        self.bits = bytearray((self.m + 7) // 8)

    def _hashes(self, item):
        h = hashlib.md5(str(item).encode()).digest()
        return [int.from_bytes(h[i:i+2], 'big') % self.m
                for i in range(0, 2 * self.k, 2)]

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

    def __contains__(self, item):
        return all(
            self.bits[pos // 8] & (1 << (pos % 8))
            for pos in self._hashes(item)
        )

Counting Bloom Filter

Standard Bloom filters can’t delete. Counting filters use counters instead of bits.

Insert "apple":   → Counter[3] +=1, Counter[7] +=1, Counter[12] +=1
Delete "apple":   → Counter[3] -=1, Counter[7] -=1, Counter[12] -=1

Use case: Dynamic sets that change over time (cache admission policies).

HyperLogLog

Estimates the number of distinct elements (cardinality) in a dataset.

How It Works

Observation: In a stream of random numbers, approximately 1 in 2^k numbers has k leading zeros.

• If you see a hash with 5 leading zeros, you’ve probably seen ~2^5 = 32 distinct items
• HyperLogLog uses multiple registers and averages them

# Simplified: count leading zeros in hash
def count_leading_zeros(hash_int):
    return (hash_int.bit_length() - 1)  # approximate

# In practice: use multiple buckets and harmonic mean

Performance

| Precision | Error Rate | Memory | |

MinHash (Min-wise Hashing)

Estimates the similarity (Jaccard index) between two sets.

J(A, B) = |A ∩ B| / |A ∪ B|

How: Similar sets hash to similar minimum values.

class MinHash:
    def __init__(self, num_hashes=128):
        self.num_hashes = num_hashes
        self.hashes = [float('inf')] * num_hashes

    def add(self, item):
        for i in range(self.num_hashes):
            # Use different hash per permutation
            h = hash(f"{i}:{item}")
            self.hashes[i] = min(self.hashes[i], h)

    def similarity(self, other):
        return sum(
            self.hashes[i] == other.hashes[i]
            for i in range(self.num_hashes)
        ) / self.num_hashes

Trade-offs

Probabilistic data structures make it feasible to answer questions about massive datasets in memory.

Advanced Bloom Filter Variants

The standard Bloom filter supports insert and membership query operations but does not support deletion. The counting Bloom filter addresses this by replacing each single bit with a small counter (typically 3-4 bits). When an element is inserted, the corresponding counters are incremented; when deleted, they are decremented. The trade-off is increased memory usage — approximately 3-4x the space of a standard Bloom filter. The counting Bloom filter is useful for caches where entries have time-to-live expiration and must be removed. The scalable Bloom filter automatically grows as more elements are inserted, maintaining a false positive rate bound by doubling the filter size when the fill ratio exceeds a threshold.

Real-World Deployments

Bloom filters appear throughout distributed systems infrastructure. Apache Cassandra uses Bloom filters for read path optimization — before accessing SSTables on disk, it checks a Bloom filter to determine whether the key might exist in that SSTable. Chromium uses a Bloom filter to maintain its list of malicious URLs: the browser downloads a compact Bloom filter representation and checks URLs locally against it, reducing network requests. Bitcoin uses Bloom filters for lightweight SPV (Simplified Payment Verification) nodes to request relevant transactions without revealing their wallet addresses. Database systems including PostgreSQL (via extensions) and RocksDB use Bloom filters to reduce unnecessary disk I/O on point lookups. Content delivery networks use Bloom filters for cache routing — determining which edge cache might hold a particular piece of content without querying all caches.

Implementation Considerations

When implementing a Bloom filter, the number of hash functions k and the filter size m determine the false positive rate for a given number of inserted elements n. The optimal k = (m/n) × ln(2) minimizes the false positive rate. Using independent hash functions is critical — a common practical approach uses two independent hash functions (e.g., MurmurHash and FNV) and generates additional hash positions through linear combination. The filter should be sized to handle the expected number of elements with a comfortable margin, as exceeding the designed capacity causes the false positive rate to climb steeply. For applications requiring deletion, consider the counting Bloom filter or the cuckoo filter, which supports deletion natively with better space efficiency than the counting Bloom filter.

Practical Implementations

Major programming languages and databases provide Bloom filter implementations. Google Guava’s BloomFilter class in Java supports configurable false positive rates and automatically chooses optimal hash function count. Redis provides Bloom filter support through the RedisBloom module with commands like BF.ADD, BF.EXISTS, and BF.RESERVE. Python’s pybloom library implements both standard and scalable Bloom filters. PostgreSQL’s bloom extension provides Bloom filter indexes for columns with many distinct values. When evaluating implementations, consider thread safety — Bloom filters are not inherently thread-safe for concurrent insert operations. The insert operation updates multiple bits, and without synchronization, concurrent reads may see inconsistent states. For high-concurrency environments, use a striped Bloom filter with multiple independently locked regions.

Space-Efficient Variants

The cuckoo filter addresses several limitations of the standard Bloom filter by using cuckoo hashing instead of bit arrays. A cuckoo filter stores fingerprints of inserted elements in a hash table using partial-key cuckoo hashing. It supports deletion naturally, uses less space than a counting Bloom filter for low false positive rates, and achieves better lookup performance. However, cuckoo filters have a maximum load factor — when too full, insertions may fail and require rehashing. The quotient filter uses a compact hash table with quotienting to reduce memory. The XOR filter uses a different mathematical approach based on solving systems of linear equations, offering smaller space than Bloom filters for static sets but cannot support dynamic insertion. Each variant optimizes for different trade-offs between space, speed, and functionality.

Frequently Asked Questions

What is the difference between a Bloom filter and a hash set? A hash set stores the actual elements and provides exact membership answers with no false positives, but uses memory proportional to the number of elements (typically 8-32 bytes per element). A Bloom filter stores only a probabilistic representation using bits and provides compact size (1-2 bytes per element) but with a configurable false positive rate. Bloom filters trade exactness for memory efficiency.

Can a Bloom filter give false negatives? No. A Bloom filter guarantees zero false negatives — if it says an element is not present, the element is definitely not in the set. False positives are possible (element reported as present when it is not), but the rate can be controlled by filter size and hash function count.

How do I choose the Bloom filter size? The required size depends on the expected number of elements (n) and desired false positive rate (p). The formula is m = -n × ln(p) / (ln(2))² bits. For 1 million elements with a 1% false positive rate, you need approximately 9.6 million bits (1.14 MB). For 0.1% false positive rate, approximately 14.4 million bits (1.72 MB).

Trees and Graphs Guide — Hash Tables Guide — Sorting Algorithms Guide