Bloom Filter

A Bloom filter is a space-efficient probabilistic data structure that answers the membership question “is element x in the set S?” with two possible answers: “definitely not in S” or “probably in S”. False positives are possible (configurable rate); false negatives are impossible. It uses a bit array of m bits and k independent hash functions; insertions and queries are O(k) — independent of |S|. Burton H. Bloom introduced it in his 1970 CACM paper as a technique to compress hyphenation dictionaries; today it’s the gatekeeper that keeps Bigtable, Cassandra, HBase, and LevelDB from issuing pointless disk reads, and it backs Chrome’s safe-browsing URL check among many other production uses.

1. Intuition — The Stamp on the Hand

You’re working the door at a club. You don’t have time to look up each guest in a list. Instead, when someone comes in, you stamp their hand in three random places out of a grid of 1,000 dots on a stamp pad. When they re-enter and you see all three of their dot positions inked, you say “yeah, this person was here.” If even one of their three positions is unmarked, you know for sure they weren’t here.

Two failure modes:

• A stranger walks up and, by coincidence, all three of their dot positions are inked from previous guests’ stamps. You’ll wave them in (a false positive).
• An actual guest cannot fail your check — every position you’d look at was stamped when they entered. So no false negatives.

That’s exactly a Bloom filter:

• Bit array = the stamp pad (m positions).
• k hash functions = the k positions to ink for each guest.
• Insert = ink all k positions.
• Query = check all k positions; if all 1, “probably yes”; if any 0, “definitely no.”

This asymmetry — false positives possible, false negatives impossible — is the property that makes Bloom filters useful as a fast prefilter in front of an expensive lookup. You only pay the expensive lookup cost on (genuine matches) ∪ (false positives), not on the much-larger set of guaranteed-misses.

2. Tiny Worked Example (m = 16 bits, k = 3)

Three hash functions h₁, h₂, h₃, each producing a value in [0, 16). Start with the bit array all zeros (positions 0..15).

initial: 0000 0000 0000 0000

Insert “apple”: suppose h₁("apple")=2, h₂("apple")=5, h₃("apple")=11. Set bits 2, 5, 11.

after apple:    0010 0100 0001 0000
position idx:    0123 4567 89..

Insert “banana”: suppose h₁=5, h₂=7, h₃=12. Set bits 5 (already 1, no-op), 7, 12.

after banana:   0010 0101 0001 1000

Query “apple”: bits 2, 5, 11 → all 1 → “probably in set” (true positive).

Query “cherry”: suppose h₁=2, h₂=7, h₃=12. All three bits happen to be 1 (set by apple/banana). The filter answers “probably in set” — but cherry was never inserted. This is a false positive.

Query “date”: suppose h₁=0, h₂=5, h₃=11. Bit 0 is 0 → answer is “definitely not in set”. Correct (date wasn’t inserted), and definitive — the filter never errs in this direction.

The crucial mental model: every insert only sets bits to 1, never clears them. So once a bit is 1, it stays 1 for the lifetime of the filter (until you rebuild). That monotonicity is what guarantees no false negatives — but it’s also why a standard Bloom filter does not support deletions (clearing a bit might also clear it for some other still-present element, breaking the no-false-negatives guarantee). See Counting Bloom Filter for the standard workaround.

3. The Algorithm

3.1 Insertion

function insert(x):
    for i in 1..k:
        idx = h_i(x) mod m
        bits[idx] = 1

3.2 Membership query

function contains(x):
    for i in 1..k:
        idx = h_i(x) mod m
        if bits[idx] == 0:
            return false                # definitely not in set
    return true                          # probably in set

3.3 The “k independent hash functions” trick

In practice you don’t compute k truly-independent hash functions. Kirsch & Mitzenmacher (2006, ESA) proved that you can simulate k functions using only two:

h_i(x) = (h_a(x) + i · h_b(x)) mod m

with no asymptotic loss in false-positive rate. So a real implementation typically calls one fast 128-bit hash (e.g., MurmurHash3, xxHash) and treats the high and low 64 bits as h_a and h_b.

4. Python Implementation

A minimal, runnable, didactic implementation:

import math
from hashlib import blake2b
 
class BloomFilter:
    """Standard Bloom filter. Two-hash trick (Kirsch-Mitzenmacher) to simulate k hashes."""
 
    def __init__(self, n_expected: int, false_positive_rate: float = 0.01):
        # Compute optimal m and k from n and target FPR.
        self.m = max(1, int(-(n_expected * math.log(false_positive_rate)) / (math.log(2) ** 2)))
        self.k = max(1, int((self.m / n_expected) * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)
        self.n = 0
 
    def _hash_pair(self, item: bytes) -> tuple[int, int]:
        h = blake2b(item, digest_size=16).digest()
        return int.from_bytes(h[:8], "big"), int.from_bytes(h[8:], "big")
 
    def _indices(self, item: bytes):
        a, b = self._hash_pair(item)
        for i in range(self.k):
            yield (a + i * b) % self.m
 
    def add(self, item: str) -> None:
        for idx in self._indices(item.encode()):
            self.bits[idx >> 3] |= 1 << (idx & 7)
        self.n += 1
 
    def __contains__(self, item: str) -> bool:
        for idx in self._indices(item.encode()):
            if not (self.bits[idx >> 3] & (1 << (idx & 7))):
                return False
        return True
 
# --- demo ----------------------------------------------------------------
if __name__ == "__main__":
    bf = BloomFilter(n_expected=1000, false_positive_rate=0.01)
    for word in ("apple", "banana", "cherry"):
        bf.add(word)
    print("apple" in bf)        # True   (true positive)
    print("durian" in bf)       # almost certainly False
    print(f"m = {bf.m} bits, k = {bf.k} hashes")

The bit array is packed eight-to-a-byte with shift-and-mask — a real implementation would use numpy.packbits or bitarray for SIMD-friendly bit operations.

5. Math — False-Positive Rate and Optimal k

This is the section that interviewers love, because the derivation is short and shows you understand the trade-offs.

After inserting n elements into a filter of m bits using k hash functions, the probability that a specific bit is still 0 is the probability that none of the kn hash invocations targeted it:

$P(\text{bit}=0)={\left(1-\frac{1}{m}\right)}^{kn}\approx e^{-kn/m}$

(The approximation uses (1 − 1/m)^x ≈ e^{−x/m} for large m.)

A false positive occurs when an element not in the set hashes to k positions that all happen to be 1. Treating the bit-states as independent (a slight oversimplification — see Bose et al. 2008 for the exact version):

$\text{FPR}=(1-P(\text{bit}=0){)}^k\approx {\left(1-e^{-kn/m}\right)}^k$

where:

• m = number of bits in the filter.
• n = number of elements inserted.
• k = number of hash functions per insert/query.
• e = base of the natural logarithm (≈ 2.71828).

Optimal k for given m, n

To minimize FPR with respect to k, take the derivative of the log:

$\ln (\text{FPR})=k\cdot \ln (1-e^{-kn/m})$

Setting d/dk = 0 (algebra omitted; full derivation in Broder & Mitzenmacher 2004) gives:

$k^{\ast }=\frac{m}{n}\ln 2\approx 0.6931\cdot \frac{m}{n}$

So if you size your filter at m = 10n bits per element, the optimal k is ≈ 7. Plugging that back into the FPR formula gives FPR ≈ 0.008 (about 0.8%) — the canonical “10 bits per element, ~1% false positives” rule of thumb you’ll see quoted everywhere.

Sizing the filter for a target FPR

Solving for m given a desired FPR ε and expected element count n:

$m=-\frac{n\ln \epsilon }{(\ln 2{)}^2}$

For ε = 0.01 (1%) and n = 1,000,000: m ≈ 9.6 million bits ≈ 1.2 MB. That’s the magic — a million-element membership filter in ~1 MB.

6. Production Use Cases

• Bigtable / HBase / Cassandra / LevelDB / RocksDB SSTable lookups. When a query needs to find a key, the system would otherwise have to read every SSTable file’s index from disk. Each SSTable carries a Bloom filter of its keys; the system consults the in-memory filter first and only reads the file on disk if the filter says “probably in set.” With a 1% FPR the disk-read rate falls by ~99% on key-misses. (Bigtable paper, OSDI 2006, §6 “Compactions”; Cassandra Bloom filter docs cited above.)

• Google Chrome’s Safe Browsing. Chrome ships with a Bloom filter (technically an enhanced version) of malicious URLs. Looking up a URL in the filter is local and fast; only a “probably bad” hit triggers a full server query. This avoids leaking your full browsing history to Google for safe URLs.

• Akamai / CDN content origins. A Bloom filter of “URLs that have ever missed once” — to avoid caching one-hit-wonders. (Maggs & Sitaraman 2015, “Algorithmic Nuggets in Content Delivery.”)

• Bitcoin SPV (Simplified Payment Verification) wallets. A wallet sends the network a Bloom filter of its addresses; the network sends back transactions matching the filter. Trades privacy for bandwidth. (Note: subsequently shown to leak more privacy than expected; BIP 37 is now considered partially deprecated.)

• Medium’s deduplication of “have you read this article before?” Maintains a Bloom filter per user of article IDs they’ve read; the recommendation pipeline filters candidates through the per-user filter so the same article isn’t surfaced twice. Trades a small false-positive rate (occasionally hiding an article the user has not actually read — invisible from the user’s perspective) for an order-of-magnitude memory reduction over storing exact read-sets.

• PostgreSQL bloom extension. Provides Bloom filter indexes for multi-column equality lookups.

• Redis BF.* commands (RedisBloom module). BF.ADD, BF.EXISTS, BF.RESERVE. Cited above.

• Password breach detection. “Have I Been Pwned” provides a downloadable Bloom filter of breached password hashes for offline check.

Version-stability note (as of 2026-05). HBase has defaulted column-family BLOOMFILTER to ROW since 0.96 — the current Reference Guide’s quickstart still shows a newly-created column family reporting BLOOMFILTER => 'ROW' (HBase book). Chromium’s chrome/browser/safe_browsing/bloom_filter.cc is still present on main; Google’s February 2024 Safe Browsing post discusses protocol changes (async checks, fewer sub-resource checks) but does not announce a switch away from the local Bloom prefilter. Cuckoo and XOR filters are increasingly used in new systems (RocksDB’s “ribbon” filter, several CDN edges) but the canonical Bigtable/Cassandra/Chrome deployments documented above remain Bloom-based today.

7. Variants

7.1 Counting Bloom Filter

Replace each bit with a small counter (typically 4 bits). Insert increments; delete decrements. Supports deletion at the cost of 4× space. Risk: counter overflow if the same element is inserted enough times.

7.2 Scalable Bloom Filter (Almeida et al. 2007)

A sequence of Bloom filters with geometrically tightening FPRs. When the current filter approaches saturation, allocate a new bigger one. Lookup checks all filters; insert goes to the newest. Supports growth without rebuild but worsens FPR over time.

7.3 Cuckoo Filter (Fan et al. 2014, CoNEXT)

Stores small fingerprints in a cuckoo hash table instead of bits. Supports deletions natively, has lower FPR than Bloom for the same space (when ε < ~3%), and is cache-friendlier. Many systems are migrating from Bloom → Cuckoo for new deployments.

7.4 Quotient Filter

Stores a quotient of the hash explicitly in a hash-table-like layout. Better cache behavior than Bloom; supports merge and resize.

7.5 XOR Filter (Graf & Lemire 2020)

Static (no insert/delete after build), but uses ~23% less space than Bloom at the same FPR. Use when the set is fixed (e.g., a published blocklist).

7.6 Partitioned Bloom Filter

Divide the m-bit array into k equal partitions, one per hash function. Slightly worse FPR theoretically, but enables some parallelism and is simpler to reason about.

8. Pitfalls

8.1 “Just Add More Hash Functions”

Increasing k beyond the optimum raises the FPR — you’re filling the bit array faster, so more bits are 1, so more queries falsely succeed. There’s a sweet spot; don’t overshoot.

8.2 Treating “Probably In Set” as “In Set”

A Bloom filter is a prefilter. The architecture must always be: filter says yes → do the authoritative check. Skipping the authoritative check turns false positives into incorrect answers.

8.3 Counting Filter Overflow

A 4-bit counter saturates at 15. If the same element is added a 16th time and you’re using saturating arithmetic, the counter stays at 15 — but its corresponding decrement on delete will (correctly) leave it at 14, mismatching reality. Use 8-bit counters or guard against duplicate inserts.

8.4 Salting / DoS Resistance

If the hash function is publicly known and an attacker controls inputs, they can craft elements that all collide on the same k bits, inflating the FPR for innocent users. Mitigation: keyed hash functions (SipHash) or salt the filter at construction.

8.5 Saturation

Once almost all bits are 1, the filter answers “probably in set” for everything — it has lost information. The optimal-k formula assumes you size the filter appropriately for the expected n; over-inserting drives FPR toward 1. If n is unknown a priori, use a Scalable Bloom Filter.

8.6 Serialization

The filter is just a bit array — serializing it is trivial. The trap: hash function choice must match between writer and reader. Codify the hash family (and seed, if keyed) in the on-disk format.

8.7 Independence Assumption

The classical FPR formula assumes bit positions are independent. They aren’t — the bound is slightly optimistic. Bose et al. 2008 give the tight formula. The error is small (a few percent at typical parameters) but matters when you’re calibrating to ε = 10⁻⁶ or below.

9. Diagram — Insert and Query Flow

flowchart TD
    X[Element x] --> H1["h₁(x) = 2"]
    X --> H2["h₂(x) = 5"]
    X --> H3["h₃(x) = 11"]
    H1 --> B[Bit array of m bits]
    H2 --> B
    H3 --> B
    B --> Q{All k bits = 1?}
    Q -->|yes| P["Probably in set<br/>(may be false positive)"]
    Q -->|no| N["Definitely not in set<br/>(no false negatives ever)"]

What this diagram shows. A single query computes k hash values from the same element x, indexes into the same bit array, and reduces by AND. The asymmetry of outcomes — yes is probabilistic, no is definitive — is the central feature of the data structure. Insert follows the same upper path but writes 1s instead of reading; that’s why no-false-negatives holds. The diagram intentionally hides the bit array’s internals: it’s just a flat array, and the only state ever maintained is “which bits are 1.”

10. Common Interview Problems

Problem	Source	What’s tested
Design a Bloom Filter	LC 705 (HashSet) extended, or as a system-design subquestion	The implementation above
Design Web Crawler	system-design round	Use a Bloom filter to dedupe seen URLs at scale
Design Distributed Cache	system-design round	Bloom filter as a “have we ever cached this?” prefilter
Design a Spell Checker	classic system question	Bloom filter for “is this word in the dictionary?” — Bloom’s original 1970 application
Design Username Suggester	system-design round	Quick “is this taken?” check; verify on positive
Design URL Shortener	system-design round	Dedup of generated short codes

11. Open Questions

• When does the Cuckoo filter’s cache-friendlier layout actually win over Bloom in production wall-clock time? Some benchmarks (Fan et al. 2014) show Cuckoo beats Bloom on large filters; others show Bloom wins for small filters that fit in L1.
• Is there a principled way to combine W-TinyLFU’s frequency sketch with a Bloom filter for cache admission policies, or are they always separate components?

12. See Also

• Hash Table — Bloom is “what if you compressed a hash set lossily”
• Hash Function Design — choice of hash matters
• Counting Bloom Filter — adds delete support
• Cuckoo Filter — modern alternative
• HyperLogLog — probabilistic cardinality (not membership)
• Count-Min Sketch — probabilistic frequency
• LSM Tree — uses Bloom filters per SSTable
• Consistent Hashing — sibling distributed-systems primitive
• SWE Interview Preparation MOC