What is a Bloom Filter?

A Bloom Filter is a space-efficient, probabilistic data structure used to test whether an element is a member of a set.

• False Positives: Possible. The filter might claim an element is in the set when it is not.
• False Negatives: Impossible. If the filter claims an element is not in the set, it is definitely not.
• Deletions: Standard Bloom Filters do not support deleting elements.

Explanation

• When storing massive sets of data (e.g., millions of malicious URLs or username registrations), storing the actual keys in memory becomes too expensive. A Bloom Filter uses a compact bit array to represent membership, discarding the keys entirely.

Real-World Analogy

• Physical Mailroom Checklist: A mailroom clerk keeps a checklist of families who have packages. Instead of writing full names, they write initials. If someone asks for a package for “John Doe” (initials JD), and the initials “JD” are on the list, there might be a package (or it could be for “Jane Davis” — a false positive). But if “JD” is not on the list, there is definitely no package (no false negative).
• Database Cache Filtering (LSM Trees / RocksDB): Before reading a heavy block file from disk to look up a key, the database queries an in-memory Bloom Filter. If it returns False, the database skips the disk read entirely.

How It Works

Core Mechanics

• A Bloom Filter consists of:
  1. A bit array of size $m$, initially all set to 0.
  2. $k$ different hash functions, each mapping a key to one of the $m$ bit positions with a uniform random distribution.

1. Insertion

• To insert an element, feed it to each of the $k$ hash functions to get $k$ indices.
• Set the bits at all these indices to 1.

2. Query (Lookup)

• To query an element, hash it using the $k$ hash functions to get $k$ indices.
• Check if the bits at all these indices are 1.
• 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.

Mathematical Formulas and Tuning

• Given:
  • $n$ = expected number of elements to be inserted.
  • $p$ = acceptable false positive probability (e.g. 0.01 for 1%).
• The optimal size of the bit array $m$ is: $m=-\frac{n\ln p}{(\ln 2{)}^2}$
• The optimal number of hash functions $k$ is: $k=\frac{m}{n}\ln 2$

Visual Walkthrough

Initial empty bit array (size $m=8$, hash functions $k=2$)

Index: 0  1  2  3  4  5  6  7
Bit:   0  0  0  0  0  0  0  0

Insert “apple” (hashes to 1 and 4)

Index: 0  1  2  3  4  5  6  7
Bit:   0  1  0  0  1  0  0  0

Insert “banana” (hashes to 4 and 6)

Index: 0  1  2  3  4  5  6  7
Bit:   0  1  0  0  1  0  1  0

Query “apple” (hashes to 1 and 4)

• Bit at 1 is 1, Bit at 4 is 1. Returns True (correct).

Query “cherry” (hashes to 1 and 6)

• Bit at 1 is 1, Bit at 6 is 1. Returns True (False Positive! “cherry” was never inserted, but both bits were set by others).

Time & Space Complexity

• Note: $k$ is the number of hash functions. Since $k$ is a small constant (typically between 3 and 10), insertion and query are effectively $O(1)$ operations.

Implementation

​

import math
 
class BloomFilter:
    def __init__(self, expected_elements, false_positive_rate):
        """
        Initializes the Bloom Filter with optimal bit-array size (m)
        and optimal number of hash functions (k).
        """
        self.n = expected_elements
        self.p = false_positive_rate
        
        # Calculate optimal size m and optimal hash count k
        self.m = int(- (self.n * math.log(self.p)) / (math.log(2) ** 2))
        self.k = max(1, int((self.m / self.n) * math.log(2)))
        
        self.bit_array = [0] * self.m
 
    def _fnv1a_hash(self, key, seed):
        """Computes an FNV-1a hash value for a key with a seed offset."""
        # FNV parameters for 64-bit hashing
        fnv_prime = 1099511628211
        fnv_offset_basis = 14695981039346656037
        
        # Standard hashing representation
        hash_val = fnv_offset_basis ^ seed
        for char in str(key):
            hash_val ^= ord(char)
            hash_val = (hash_val * fnv_prime) & 0xFFFFFFFFFFFFFFFF
        return hash_val % self.m
 
    def insert(self, item):
        """Inserts an item by setting bits at hashed indices."""
        for i in range(self.k):
            idx = self._fnv1a_hash(item, i)
            self.bit_array[idx] = 1
 
    def query(self, item):
        """
        Queries membership.
        Returns False if definitely not in set.
        Returns True if probably in set.
        """
        for i in range(self.k):
            idx = self._fnv1a_hash(item, i)
            if self.bit_array[idx] == 0:
                return False
        return True
 
# Example Usage
if __name__ == "__main__":
    bf = BloomFilter(expected_elements=1000, false_positive_rate=0.01)
    print(f"Optimal array size: {bf.m} bits, hash count: {bf.k}")
    
    bf.insert("apple")
    bf.insert("banana")
    
    print("Query apple:", bf.query("apple"))    # True
    print("Query banana:", bf.query("banana"))  # True
    print("Query cherry:", bf.query("cherry"))  # False (most likely)

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
 
class BloomFilter {
private:
    int n;
    double p;
    int m;
    int k;
    std::vector<bool> bitArray;
 
    // Computes an FNV-1a hash value for a key with a seed offset
    int fnv1aHash(const std::string& key, int seed) const {
        unsigned long long fnv_prime = 1099511628211ULL;
        unsigned long long hash_val = 14695981039346656037ULL ^ seed;
        
        for (char char_byte : key) {
            hash_val ^= static_cast<unsigned char>(char_byte);
            hash_val *= fnv_prime;
        }
        return static_cast<int>(hash_val % m);
    }
 
public:
    BloomFilter(int expectedElements, double falsePositiveRate) 
        : n(expectedElements), p(falsePositiveRate) {
        
        // Calculate optimal size m and optimal hash count k
        m = static_cast<int>(- (n * std::log(p)) / (std::log(2) * std::log(2)));
        k = std::max(1, static_cast<int>((m / static_cast<double>(n)) * std::log(2)));
        
        bitArray.assign(m, false);
    }
 
    int getBitSize() const { return m; }
    int getHashCount() const { return k; }
 
    // Inserts an item by setting bits at hashed indices
    void insert(const std::string& item) {
        for (int i = 0; i < k; ++i) {
            int idx = fnv1aHash(item, i);
            bitArray[idx] = true;
        }
    }
 
    // Queries membership
    bool query(const std::string& item) const {
        for (int i = 0; i < k; ++i) {
            int idx = fnv1aHash(item, i);
            if (!bitArray[idx]) {
                return false;
            }
        }
        return true;
    }
};
 
int main() {
    BloomFilter bf(1000, 0.01);
    std::cout << "Optimal array size: " << bf.getBitSize() << " bits, hash count: " << bf.getHashCount() << "\n";
 
    bf.insert("apple");
    bf.insert("banana");
 
    std::cout << std::boolalpha;
    std::cout << "Query apple: " << bf.query("apple") << "\n";    // true
    std::cout << "Query banana: " << bf.query("banana") << "\n";  // true
    std::cout << "Query cherry: " << bf.query("cherry") << "\n";  // false
 
    return 0;
}

​

When to Use

✅ Use Bloom Filters When:

• You need to reduce expensive disk lookups, network requests, or database scans by failing fast for non-existent keys (e.g. CDNs checking for cached content).
• Memory is highly constrained, and storing the keys themselves is impossible or impractical.
• False positives are acceptable, and you have a reliable secondary source to confirm true membership (e.g. a database search).

❌ Do NOT Use Bloom Filters When:

• Deleting elements is a strict requirement (use a Counting Bloom Filter instead).
• False positives are absolutely unacceptable (e.g. bank account balance verification or authentication systems).
• You need to list or iterate over all items currently stored in the set.

Variations & Related Concepts

• Counting Bloom Filter: Replaces each bit in the array with a small counter. Insertion increments the counter, and deletion decrements it, allowing dynamic item removal.
• Cuckoo Filter: A newer alternative using cuckoo hashing tables to store fingerprints. It supports deletions and achieves better space efficiency for low false positive rates.
• Quotient Filter: A cache-friendly alternative that stores fingerprints in a hash table using quotienting, supporting resizing.

Key Takeaways

• Bloom Filters provide space-efficient membership testing with zero false negatives but possible false positives.
• Optimal sizing ($m$) and hashing count ($k$) depend on the expected element count ($n$) and desired error rate ($p$).
• Built using simple, fast non-cryptographic hashing (like FNV-1a or MurmurHash).
• Crucial component in databases, CDNs, network routers, and caching layers.

More Learn

GitHub & Webs

• Wikipedia → Bloom filter
• GeeksforGeeks → Bloom Filters - Introduction and Implementation