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.
| Operation | Complexity |
|---|---|
| Access | N/A |
| Search | O(k) |
| Insertion | O(k) |
| Deletion | Not supported (standard) |
| Space | O(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,xis 100% definitely NOT in the set (zero false negatives!). - If it answers
true,xis 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.