AntInLoop

Bloom Filter (Probabilistic Set) Data Structure

A Bloom Filter is a space-efficient probabilistic bit-array data structure that tests set membership in O(k) time with zero false negatives and a tunable, low false-positive rate.

OperationComplexity
AccessN/A
SearchO(k)
InsertionO(k)
DeletionNot supported (standard)
SpaceO(m) bits

Interactive Visualizer · C++ / Python / Java / JS Code

Bloom Filter (Probabilistic Set)

A Bloom Filter is an ultra-compact probabilistic data structure that answers "is x in the set?" using just a bit array of $m$ bits and $k$ independent hash functions:

  • If it answers false, x is 100% definitely NOT in the set (zero false negatives!).
  • If it answers true, x is probably in the set (small tunable false-positive probability $p$).

With just ~9.6 bits per element ($m / n \approx 10$, $k = 7$), a Bloom Filter achieves a 1% false-positive rate—saving gigabytes of RAM in databases like RocksDB, Cassandra, and PostgreSQL!

At a Glance

| Property | Value |

| :--- | :--- |

| insert(x) / mightContain(x) | $O(k)$ ($k$ hash evaluations, typically $k \in [3, 10]$) |

| Deletion | Not supported in standard Bloom Filter (use Counting Bloom Filter) |

| Optimal Number of Hashes | $k = \frac{m}{n} \ln 2 \approx 0.693 \frac{m}{n}$ |

| Optimal Bit Array Size | $m = -\frac{n \ln p}{(\ln 2)^2}$ |

---

Kirsch–Mitzenmacher Double-Hashing Trick

You don't need $k$ separate hash functions! Computing just two independent hashes $h_1(x)$ and $h_2(x)$ and probing:

$g_i(x) = \big(h_1(x) + i \cdot h_2(x)\big) \bmod m \qquad (0 \le i < k)$

gives the exact same asymptotic false-positive rate with minimal CPU work!

---

Practice Problems

Easy

1. Standard Bloom Filter Implementation (Kirsch–Mitzenmacher Double Hashing)

Implement a BloomFilter with add(string) and mightContain(string) using k double-hashed bit positions.

Approach: Store std::vector<bool> bits(m) and probe (h1 + i * h2) % m for i = 0..k-1. Time: $O(k)$ per op. Space: $m$ bits.

<details>

<summary>Show C++ Solution</summary>

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

class BloomFilter {
    std::vector<bool> bits;
    size_t m, k;

    static uint64_t hash1(const std::string& s) {
        uint64_t h = 1469598103934665603ULL;
        for (unsigned char c : s) { h ^= c; h *= 1099511628211ULL; }
        return h;
    }
    static uint64_t hash2(const std::string& s) {
        uint64_t h = 5381;
        for (unsigned char c : s) h = ((h << 5) + h) + c;
        return h | 1ULL; // ensure odd step
    }

public:
    BloomFilter(size_t numBits, size_t numHashes) : bits(numBits, false), m(numBits), k(numHashes) {}

    void add(const std::string& s) {
        uint64_t a = hash1(s), b = hash2(s);
        for (size_t i = 0; i < k; ++i) bits[(a + i * b) % m] = true;
    }

    bool mightContain(const std::string& s) const {
        uint64_t a = hash1(s), b = hash2(s);
        for (size_t i = 0; i < k; ++i) {
            if (!bits[(a + i * b) % m]) return false;
        }
        return true;
    }
};

int main() {
    BloomFilter bf(1024, 5);
    bf.add("apple"); bf.add("banana"); bf.add("cherry");
    std::cout << std::boolalpha << bf.mightContain("banana") << " "
              << bf.mightContain("durian") << "\n"; // true false
    return 0;
}

</details>

2. Counting Bloom Filter (Supporting Deletion)

Extend a Bloom Filter to support remove(string) by replacing each bit with an 8-bit counter.

Approach: Increment counters[pos] on add, decrement on remove (only if present), and check counters[pos] > 0 on mightContain. Time: $O(k)$.

<details>

<summary>Show C++ Solution</summary>

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

class CountingBloomFilter {
    std::vector<uint8_t> cnt;
    size_t m, k;
    static uint64_t h1(const std::string& s) {
        uint64_t h = 1469598103934665603ULL;
        for (unsigned char c : s) { h ^= c; h *= 1099511628211ULL; }
        return h;
    }
    static uint64_t h2(const std::string& s) {
        uint64_t h = 5381;
        for (unsigned char c : s) h = ((h << 5) + h) + c;
        return h | 1ULL;
    }
public:
    CountingBloomFilter(size_t numBuckets, size_t numHashes) : cnt(numBuckets, 0), m(numBuckets), k(numHashes) {}
    void add(const std::string& s) {
        uint64_t a = h1(s), b = h2(s);
        for (size_t i = 0; i < k; ++i) ++cnt[(a + i * b) % m];
    }
    void remove(const std::string& s) {
        if (!mightContain(s)) return;
        uint64_t a = h1(s), b = h2(s);
        for (size_t i = 0; i < k; ++i) --cnt[(a + i * b) % m];
    }
    bool mightContain(const std::string& s) const {
        uint64_t a = h1(s), b = h2(s);
        for (size_t i = 0; i < k; ++i) if (cnt[(a + i * b) % m] == 0) return false;
        return true;
    }
};

int main() {
    CountingBloomFilter cbf(512, 4);
    cbf.add("alpha"); cbf.add("beta");
    cbf.remove("alpha");
    std::cout << std::boolalpha << cbf.mightContain("alpha") << " "
              << cbf.mightContain("beta") << "\n"; // false true
    return 0;
}

</details>

---

Related Structures & Algorithms

  • Hash Set — exact membership testing without false positives.
  • Hash Table — exact key-value storage.