Bloom Filters & Probabilistic Indexing

When handling billions of key-value lookups in high-throughput databases (like RocksDB, Apache Cassandra, PostgreSQL, and Google Bigtable), checking whether a key exists in disk storage before executing an expensive I/O operation is a major bottleneck.

A Bloom Filter is a space-efficient probabilistic data structure invented by Burton Howard Bloom in 1970 that tests set membership in $O(k)$ constant time using a compact bit vector and $k$ independent hash functions.

1. Summary & Key Takeaways

• Zero False Negatives: If the Bloom Filter returns false (“Definitely Not in Set”), the element is guaranteed 100% not to exist. The system can safely bypass expensive disk lookups!
• Controlled False Positive Rate ($\epsilon$): If the filter returns true (“Maybe in Set”), the element might exist, or a hash collision occurred. The false positive probability is bounded mathematically: $\epsilon \approx \left(1 - e^{-kn/m}\right)^k$ where $m$ is the bit array size, $n$ is the number of inserted keys, and $k$ is the number of hash functions.
• Space Efficiency: Requires only ~10 bits per element for a 1% false positive rate, orders of magnitude smaller than hash sets or B-Trees.

2. Interactive Bloom Filter Simulator

Insert keys into the 16-bit array below using independent hash functions, and run membership queries to observe definite negatives, true positives, and probabilistic false positives!

3. Bloom Filter Query Flowchart

graph TD
    KEY["Query Key"] --> HASHES["Compute Bit Indices h1(x), h2(x)... hk(x)"]
    HASHES --> COND{"Are ALL bits set to 1?"}
    COND -->|No| NO["DEFINITELY NOT IN SET (100% Certainty - Bypass Disk)"]
    COND -->|Yes| MAYBE["MAYBE IN SET (Execute Disk/DB Index Lookup)"]

4. Multi-Language Implementation Code

Compare production Bloom Filter implementations across C++, Python, Java, Go, Rust, and TypeScript below:

#include <iostream>
#include <vector>
#include <string>
#include <functional>

class BloomFilter {
private:
    std::vector<bool> bitArray;
    size_t size;

    size_t hash1(const std::string& key) const {
        return std::hash<std::string>{}(key) % size;
    }

    size_t hash2(const std::string& key) const {
        size_t hash = 5381;
        for (char c : key) hash = ((hash << 5) + hash) + c;
        return hash % size;
    }

public:
    BloomFilter(size_t bits) : size(bits), bitArray(bits, false) {}

    void insert(const std::string& key) {
        bitArray[hash1(key)] = true;
        bitArray[hash2(key)] = true;
    }

    bool contains(const std::string& key) const {
        // Guaranteed 100% false negative free!
        return bitArray[hash1(key)] && bitArray[hash2(key)];
    }
};

5. Probabilistic vs Exact Search Structures