Bloom Filters

The Membership Testing Problem

In many systems, we need to quickly check if an element belongs to a set:

• Cache lookup: Is this key in the cache?
• Duplicate detection: Have we seen this request before?
• Database query: Does this record exist?
• Spell checking: Is this word in the dictionary?

Traditional Approach:

• Use a hash set: O(1) lookup, but requires storing all elements
• For 1 billion elements, need ~8GB of memory (assuming 8 bytes per element)

The Challenge: What if we need to check membership for billions of elements but can’t afford to store them all? What if we can tolerate occasional false positives but never false negatives?

What is a Bloom Filter?

A Bloom filter is a probabilistic data structure that provides space-efficient membership testing. It can tell you:

• “Definitely not in set” - 100% accurate
• “Possibly in set” - might be a false positive

Key Properties:

• Space-efficient: Uses only a few bits per element
• Fast operations: O(k) time complexity (k = number of hash functions)
• No false negatives: If filter says “no”, element is definitely not in set
• False positives possible: If filter says “yes”, element might not be in set (need to verify)

Simple Analogy

Think of a Bloom filter like a guest list at a party:

• The bit array is like a checklist with many boxes
• Adding an element is like checking boxes for that guest’s name
• Checking membership is like verifying if boxes are checked for a name
• If boxes are checked, the guest might be on the list (could be coincidence)
• If boxes are not checked, the guest is definitely not on the list

How Bloom Filters Work

Initialization

1. Create a bit array of size m (all bits initialized to 0)
2. Choose k independent hash functions
3. Each hash function maps elements to positions in the bit array (0 to m-1)

Adding an Element

1. Hash the element with all k hash functions
2. Set the k corresponding bits to 1

Checking Membership

1. Hash the element with all k hash functions
2. Check if all k corresponding bits are 1
3. If all bits are 1: Element is possibly in the set (might be false positive)
4. If any bit is 0: Element is definitely not in the set

Why False Positives Occur:

When checking membership, if all bits are set to 1, it could mean:

• The element was added (correct)
• Other elements happened to set those same bits (false positive)

Why No False Negatives:

If an element was added, all its bits were set to 1. If we check and find any bit is 0, the element was definitely not added.

Bloom Filter Implementation

💡 Tip: Click dropdown to switch between languages

Python

Python

"bloom_filter.py

import mmh3  # MurmurHash3
import math
from typing import List

class BloomFilter:
    """Bloom filter implementation"""

    def __init__(self, capacity: int, error_rate: float = 0.01):
        """
        Initialize Bloom filter

        Args:
            capacity: Expected number of elements
            error_rate: Desired false positive rate (e.g., 0.01 = 1%)
        """
        # Calculate optimal parameters
        # m = -n * ln(p) / (ln(2)^2) where n=capacity, p=error_rate
        self.m = int(-capacity * math.log(error_rate) / (math.log(2) ** 2))

        # k = (m/n) * ln(2) where n=capacity
        self.k = int((self.m / capacity) * math.log(2))

        # Ensure k is at least 1
        self.k = max(1, self.k)

        # Bit array (using list of integers, each representing 32 bits)
        self.bit_array = [0] * ((self.m + 31) // 32)
        self.size = 0

    def _get_bit(self, index: int) -> bool:
        """Get bit at index"""
        array_index = index // 32
        bit_index = index % 32
        return (self.bit_array[array_index] >> bit_index) & 1 == 1

    def _set_bit(self, index: int):
        """Set bit at index to 1"""
        array_index = index // 32
        bit_index = index % 32
        self.bit_array[array_index] |= (1 << bit_index)

    def _hash(self, item: str, seed: int) -> int:
        """Hash item with seed"""
        return mmh3.hash(item, seed) % self.m

    def add(self, item: str):
        """Add item to Bloom filter"""
        for i in range(self.k):
            index = self._hash(item, i)
            self._set_bit(index)
        self.size += 1

    def contains(self, item: str) -> bool:
        """Check if item might be in Bloom filter"""
        for i in range(self.k):
            index = self._hash(item, i)
            if not self._get_bit(index):
                return False  # Definitely not in set
        return True  # Possibly in set (might be false positive)

    def get_stats(self) -> dict:
        """Get Bloom filter statistics"""
        return {
            'capacity': self.size,
            'bit_array_size': self.m,
            'hash_functions': self.k,
            'bits_per_element': self.m / max(1, self.size)
        }

# Usage
bloom = BloomFilter(capacity=10000, error_rate=0.01)

# Add elements
bloom.add("user-123")
bloom.add("user-456")
bloom.add("order-789")

# Check membership
print(bloom.contains("user-123"))  # True (possibly in set)
print(bloom.contains("user-999"))  # False (definitely not in set)

# Get statistics
stats = bloom.get_stats()
print(f"Bit array size: {stats['bit_array_size']}")
print(f"Hash functions: {stats['hash_functions']}")

Java

"BloomFilter.java

import java.util.BitSet;
import java.util.Random;

public class BloomFilter {
    private final BitSet bitSet;
    private final int bitArraySize;
    private final int numHashFunctions;
    private final int[] hashSeeds;
    private int size;

    public BloomFilter(int capacity, double errorRate) {
        // Calculate optimal parameters
        // m = -n * ln(p) / (ln(2)^2)
        this.bitArraySize = (int) (-capacity * Math.log(errorRate) / (Math.log(2) * Math.log(2)));

        // k = (m/n) * ln(2)
        this.numHashFunctions = Math.max(1, (int) ((bitArraySize / (double) capacity) * Math.log(2)));

        this.bitSet = new BitSet(bitArraySize);
        this.hashSeeds = new int[numHashFunctions];

        // Generate random seeds for hash functions
        Random random = new Random();
        for (int i = 0; i < numHashFunctions; i++) {
            hashSeeds[i] = random.nextInt();
        }
    }

    private int hash(String item, int seed) {
        // Simple hash function (in production, use better hash like MurmurHash)
        int hash = item.hashCode() ^ seed;
        return Math.abs(hash) % bitArraySize;
    }

    public void add(String item) {
        // Add item to Bloom filter
        for (int i = 0; i < numHashFunctions; i++) {
            int index = hash(item, hashSeeds[i]);
            bitSet.set(index);
        }
        size++;
    }

    public boolean contains(String item) {
        // Check if item might be in Bloom filter
        for (int i = 0; i < numHashFunctions; i++) {
            int index = hash(item, hashSeeds[i]);
            if (!bitSet.get(index)) {
                return false; // Definitely not in set
            }
        }
        return true; // Possibly in set (might be false positive)
    }

    public int getSize() {
        return size;
    }

    public int getBitArraySize() {
        return bitArraySize;
    }

    public int getNumHashFunctions() {
        return numHashFunctions;
    }
}

// Usage
BloomFilter bloom = new BloomFilter(10000, 0.01);

bloom.add("user-123");
bloom.add("user-456");
bloom.add("order-789");

System.out.println(bloom.contains("user-123")); // true
System.out.println(bloom.contains("user-999")); // false

TypeScript

bloom-filter.ts

class BloomFilter {
    // Bloom filter implementation
    private bitArray: Uint32Array;
    private bitArraySize: number;
    private numHashFunctions: number;
    private hashSeeds: number[];
    private size: number;

    constructor(capacity: number, errorRate: number = 0.01) {
        // Calculate optimal parameters
        // m = -n * ln(p) / (ln(2)^2)
        this.bitArraySize = Math.ceil(
            -capacity * Math.log(errorRate) / (Math.log(2) ** 2)
        );

        // k = (m/n) * ln(2)
        this.numHashFunctions = Math.max(
            1,
            Math.ceil((this.bitArraySize / capacity) * Math.log(2))
        );

        // Bit array (using Uint32Array, each element represents 32 bits)
        this.bitArray = new Uint32Array(Math.ceil(this.bitArraySize / 32));
        this.hashSeeds = [];
        this.size = 0;

        // Generate random seeds for hash functions
        for (let i = 0; i < this.numHashFunctions; i++) {
            this.hashSeeds.push(Math.floor(Math.random() * 2147483647));
        }
    }

    private getBit(index: number): boolean {
        // Get bit at index
        const arrayIndex = Math.floor(index / 32);
        const bitIndex = index % 32;
        return (this.bitArray[arrayIndex] & (1 << bitIndex)) !== 0;
    }

    private setBit(index: number): void {
        // Set bit at index to 1
        const arrayIndex = Math.floor(index / 32);
        const bitIndex = index % 32;
        this.bitArray[arrayIndex] |= (1 << bitIndex);
    }

    private hash(item: string, seed: number): number {
        // Hash item with seed (simple hash, use better hash in production)
        let hash = 0;
        for (let i = 0; i < item.length; i++) {
            hash = ((hash << 5) - hash + item.charCodeAt(i) + seed) | 0;
        }
        return Math.abs(hash) % this.bitArraySize;
    }

    add(item: string): void {
        // Add item to Bloom filter
        for (let i = 0; i < this.numHashFunctions; i++) {
            const index = this.hash(item, this.hashSeeds[i]);
            this.setBit(index);
        }
        this.size++;
    }

    contains(item: string): boolean {
        // Check if item might be in Bloom filter
        for (let i = 0; i < this.numHashFunctions; i++) {
            const index = this.hash(item, this.hashSeeds[i]);
            if (!this.getBit(index)) {
                return false; // Definitely not in set
            }
        }
        return true; // Possibly in set (might be false positive)
    }

    getStats() {
        // Get Bloom filter statistics
        return {
            capacity: this.size,
            bitArraySize: this.bitArraySize,
            hashFunctions: this.numHashFunctions,
            bitsPerElement: this.bitArraySize / Math.max(1, this.size)
        };
    }
}

// Usage
const bloom = new BloomFilter(10000, 0.01);

bloom.add("user-123");
bloom.add("user-456");
bloom.add("order-789");

console.log(bloom.contains("user-123")); // true
console.log(bloom.contains("user-999")); // false

C++

bloom_filter.cpp

#include <vector>
#include <bitset>
#include <cmath>
#include <random>
#include <string>
#include <functional>

class BloomFilter {
private:
    std::vector<bool> bitArray;
    int bitArraySize;
    int numHashFunctions;
    std::vector<int> hashSeeds;
    int size;

    int hash(const std::string& item, int seed) {
        // Hash item with seed
        std::hash<std::string> hasher;
        size_t hashValue = hasher(item);
        return (hashValue ^ seed) % bitArraySize;
    }

public:
    BloomFilter(int capacity, double errorRate = 0.01) {
        // Calculate optimal parameters
        // m = -n * ln(p) / (ln(2)^2)
        bitArraySize = static_cast<int>(
            -capacity * std::log(errorRate) / (std::log(2) * std::log(2))
        );

        // k = (m/n) * ln(2)
        numHashFunctions = std::max(1, static_cast<int>(
            (bitArraySize / static_cast<double>(capacity)) * std::log(2)
        ));

        bitArray.resize(bitArraySize, false);

        // Generate random seeds for hash functions
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(0, 2147483647);

        for (int i = 0; i < numHashFunctions; i++) {
            hashSeeds.push_back(dis(gen));
        }

        size = 0;
    }

    void add(const std::string& item) {
        // Add item to Bloom filter
        for (int i = 0; i < numHashFunctions; i++) {
            int index = hash(item, hashSeeds[i]);
            bitArray[index] = true;
        }
        size++;
    }

    bool contains(const std::string& item) {
        // Check if item might be in Bloom filter
        for (int i = 0; i < numHashFunctions; i++) {
            int index = hash(item, hashSeeds[i]);
            if (!bitArray[index]) {
                return false; // Definitely not in set
            }
        }
        return true; // Possibly in set (might be false positive)
    }

    int getSize() const { return size; }
    int getBitArraySize() const { return bitArraySize; }
    int getNumHashFunctions() const { return numHashFunctions; }
};

// Usage
int main() {
    BloomFilter bloom(10000, 0.01);

    bloom.add("user-123");
    bloom.add("user-456");
    bloom.add("order-789");

    std::cout << bloom.contains("user-123") << std::endl; // 1 (true)
    std::cout << bloom.contains("user-999") << std::endl; // 0 (false)

    return 0;
}

C#

BloomFilter.cs

using System;
using System.Collections;

public class BloomFilter {
    // Bloom filter implementation
    private readonly BitArray bitArray;
    private readonly int bitArraySize;
    private readonly int numHashFunctions;
    private readonly int[] hashSeeds;
    private int size;

    public BloomFilter(int capacity, double errorRate = 0.01) {
        // Calculate optimal parameters
        // m = -n * ln(p) / (ln(2)^2)
        this.bitArraySize = (int)Math.Ceiling(
            -capacity * Math.Log(errorRate) / (Math.Log(2) * Math.Log(2))
        );

        // k = (m/n) * ln(2)
        this.numHashFunctions = Math.Max(1, (int)Math.Ceiling(
            (bitArraySize / (double)capacity) * Math.Log(2)
        ));

        this.bitArray = new BitArray(bitArraySize, false);
        this.hashSeeds = new int[numHashFunctions];

        // Generate random seeds for hash functions
        Random random = new Random();
        for (int i = 0; i < numHashFunctions; i++) {
            hashSeeds[i] = random.Next();
        }

        this.size = 0;
    }

    private int Hash(string item, int seed) {
        // Hash item with seed
        int hash = item.GetHashCode() ^ seed;
        return Math.Abs(hash) % bitArraySize;
    }

    public void Add(string item) {
        // Add item to Bloom filter
        for (int i = 0; i < numHashFunctions; i++) {
            int index = Hash(item, hashSeeds[i]);
            bitArray[index] = true;
        }
        size++;
    }

    public bool Contains(string item) {
        // Check if item might be in Bloom filter
        for (int i = 0; i < numHashFunctions; i++) {
            int index = Hash(item, hashSeeds[i]);
            if (!bitArray[index]) {
                return false; // Definitely not in set
            }
        }
        return true; // Possibly in set (might be false positive)
    }

    public int Size => size;
    public int BitArraySize => bitArraySize;
    public int NumHashFunctions => numHashFunctions;
}

// Usage
var bloom = new BloomFilter(10000, 0.01);

bloom.Add("user-123");
bloom.Add("user-456");
bloom.Add("order-789");

Console.WriteLine(bloom.Contains("user-123")); // True
Console.WriteLine(bloom.Contains("user-999")); // False

Optimal Parameters

The false positive rate depends on:

• m: Size of bit array
• k: Number of hash functions
• n: Number of elements added

Optimal values:

• m = -n × ln(p) / (ln(2)²) where p = desired false positive rate
• k = (m/n) × ln(2)

Example:

• 1 million elements, 1% false positive rate
• m ≈ 9.6 million bits ≈ 1.2 MB
• k ≈ 7 hash functions
• Only ~1.2 bytes per element!

Use Cases

Cache Filtering

Before checking expensive cache (like Redis), use Bloom filter to quickly check if key might exist. Reduces cache lookup overhead.

Example: Check Bloom filter first. If “no”, skip cache lookup. If “yes”, check actual cache (might be false positive, but that’s okay).

Duplicate Detection

Track which requests/items have been processed. Bloom filter says “definitely new” or “possibly seen”. For “possibly seen”, verify with actual storage.

Database Query Optimization

Before expensive database query, check Bloom filter. If “definitely not”, skip query. If “possibly yes”, execute query.

Network Routing

Check if route exists before expensive routing table lookup. Bloom filter provides fast pre-filtering.

Counting Bloom Filter

Standard Bloom filters can’t remove elements. Counting Bloom filter uses counters instead of bits, enabling deletion:

• Each position stores a counter instead of a bit
• Add: Increment counters
• Remove: Decrement counters
• Check: Verify all counters > 0

Trade-off: Uses more space (counters instead of bits) but enables deletion.

Trade-offs

Advantages:

• Space-efficient (few bits per element)
• Fast operations (O(k) time)
• No false negatives
• Scales well

Disadvantages:

• False positives possible
• Can’t remove elements (unless counting Bloom filter)
• Can’t list elements
• Requires multiple hash functions

Key Takeaways

Space Efficient

Uses only a few bits per element. For 1M elements with 1% false positive rate, needs only ~1.2MB.

No False Negatives

If Bloom filter says “no”, element is definitely not in set. If says “yes”, might be false positive.

Fast Operations

Add and check operations are O(k) where k is number of hash functions (typically 3-10).

Probabilistic

Answers “possibly in set” or “definitely not in set”. False positives possible, false negatives impossible.

---

Next Steps

• Learn Distributed Caching - Bloom filters used for cache filtering
• Master Consistent Hashing - another space-efficient data structure
• Understand Database Indexing - Bloom filters used in database indexes