1. One-Liner
A Bloom filter uses k hash functions into a bit array to answer “maybe in set” with no false negatives for inserts (standard form) but possible false positives.
2. The Problem It Solves
Exact sets cost space; many systems only need cheap negative answers (e.g., avoid disk lookups) and tolerate rare false positives.
3. The Core Idea
Insert: set all k positions h_i(x) to 1. Query: all must be 1 to return “maybe yes”; any 0 → definitely no.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1 | Choose m bits, k hashes |
| 2 | Add: OR bits at all h_i(x) |
| 3 | Query: AND of those bits |
| 4 | Tune m,k for desired FP rate |
5. Dry Run Example
m=8, k=2, insert “foo” sets bits 1,5; query “foo” sees both 1; query “bar” might still hit 1 by accident → false positive.
6. Key Properties
| Property | Value |
|---|---|
| Space | Sublinear in n items |
| Delete | Not standard (need counting / other structures) |
| FP rate | Drops with larger m, optimal k |
7. Where It Is Used
| Domain | Use |
|---|---|
| Databases | Avoid disk reads (HBase, Cassandra) |
| Networking | Chrome safe-browsing, caches |
8. Interview Tips
k hashes, FP formula intuition, counting Bloom for delete, alternatives (Cuckoo filter).
9. Comparison with Other Algorithms
| Structure | False positives |
|---|---|
| Hash set | None |
| Bloom | Yes |
| Quotient filter | Different tradeoff |
10. Complexity
| Metric | Value |
|---|---|
| Insert/Query | O(k) time, O(m) bits |
| Space | O(n log(1/ε)) order-wise |
Implementation Example (PYTHON)
class Bloom:
def __init__(self, m=1024, k=3):
self.m, self.k, self.bits = m, k, bytearray(m // 8 + 1)
def _h(self, x, i): return hash(f'{x}:{i}') % self.m
def add(self, x):
for i in range(self.k):
j = self._h(x, i); self.bits[j // 8] |= 1 << (j % 8)
def maybe(self, x):
for i in range(self.k):
j = self._h(x, i)
if not ((self.bits[j // 8] >> (j % 8)) & 1):
return False
return True