How Bloom Filters Work: The Probabilistic Set

Scenario context

Imagine a nightclub with a strict guestlist. The bouncer has a system with ten switches (0 or 1). When Alice registers, her name is hashed by three different functions: switch 2, 5, and 8 are turned ON. When Bob registers, switch 1, 5, and 9 are turned ON.

At the door: "Is Charlie here?"

• Hash Charlie → switches 2, 7, 4.
• Switch 7 is OFF. Definitely not registered. (No false negative.)

"Is Alice here?"

• Has…

This walkthrough focuses on The Nightclub Guestlist with No Memory.

Before making a design choice, clarify:

• Imagine a nightclub with a strict guestlist.
• The bouncer has a system with ten switches (0 or 1).
• When Alice registers, her name is hashed by three different functions: switch 2, 5, and 8 are turned ON.

Concepts in play: hash-tables-and-bloom-filters, btree-vs-lsmtree, database-indexing, caching

Stage 1 — Bit Arrays, Hash Functions, and the Two Operations

• A Bloom filter has just two parts and two operations — that's the whole structure.
• The two parts: - A bit array of size m , initialized to all zeros.
• • k independent hash functions , each of which maps any element to one position in the array.
• The two operations: Insert(x): Run x through all k hash functions.

Observable outcome: The two operations: Insert(x): Run x through all k hash functions.

Stage 2 — How Three Hash Functions Set Bits in a Bit Array

• Inserting "Alice" into a 10-bit Bloom filter with 3 hash functions: Querying "Charlie": Querying "Dave" (false positive case): 📊 Bloom Filter Insert: Hash Functions Set Bits This diagram shows how a single insert fans…
• All three hash operations happen for every insert — there are no shortcuts.
• The critical takeaway is that these bit writes are the only state change: once set, a bit is never cleared, which is precisely why false negatives are structurally impossible.
• 📊 Bloom Filter Lookup: Check All Bits This diagram shows the asymmetric nature of a Bloom filter query: the result is either a definitive "no" (any zero bit proves absence) or a probabilistic "yes" (all bits set could…

Position:    0 1 2 3 4 5 6 7 8 9
Initial:     0 0 0 0 0 0 0 0 0 0

hash1("Alice") = 2 → set bit 2
hash2("Alice") = 5 → set bit 5
hash3("Alice") = 8 → set bit 8

After Alice:  0 0 1 0 0 1 0 0 1 0

hash1("Charlie") = 2 → bit 2 is 1 ✓
hash2("Charlie") = 7 → bit 7 is 0 ✗  → DEFINITELY NOT IN SET

Observable outcome: 📊 Bloom Filter Lookup: Check All Bits This diagram shows the asymmetric nature of a Bloom filter query: the result is either a definitive "no" (any zero bit proves absence) or a probabilistic "yes" (all bits set could…

Stage 3 — False Positives Are Guaranteed; False Negatives Are Not

• Why can you never have a false negative?
• When you insert an element, you set specific bits.
• When you query the same element, you check the exact same bits.
• Those bits can only be 1 (we set them).

Observable outcome: Those bits can only be 1 (we set them).

Stage 4 — Insert and Query Flow

• The following diagram shows how a single element travels through a Bloom filter for both insert and query operations.
• The key branch at query time — "are all bits 1?" — is where the probabilistic guarantee lives.
• The insert path is unconditional — it always writes.
• The query path is the only place a decision is made.

flowchart TD
    Insert["Insert: hash(element)  k bit positions"]
    Insert --> SetBits[Set bits at positions h1, h2, h3 = 1]

    Query["Query: hash(element)  k bit positions"]
    Query --> CheckBits{All k bits = 1?}
    CheckBits -- "No (any bit = 0)" --> Absent["DEFINITELY NOT in set (no false negatives)"]
    CheckBits -- "Yes (all bits = 1)" --> Present["PROBABLY in set (may be false positive)"]

Observable outcome: The query path is the only place a decision is made.

Stage 5 — Deep Dive: Sizing a Bloom Filter—Choosing m and k

• Given $n$ expected elements and desired false positive rate $p$: $$m = -\frac{n \ln p}{(\ln 2)^2} \qquad k = \frac{m}{n} \ln 2$$ Example: 1 million elements, 1% false positives - $m \approx 9.585 \times 10^6$ bits ≈ 1.2…
• The Bloom filter is 80× smaller.

Observable outcome: The Bloom filter is 80× smaller.

Stage 6 — Real-World Applications: Bloom Filters in Production

Observable outcome: You can explain how “Real-World Applications: Bloom Filters in Production” changes the architecture or implementation path.

End-to-end outcome

Imagine a nightclub with a strict guestlist.

Alternatives considered

Decision Guide: Bloom Filter vs Hash Set

Decision Guide: Bloom Filter vs Hash Set

Failure and degraded modes

Trade-offs & Failure Modes: Bloom Filter Limitations

• Detection: Trade-offs & Failure Modes: Bloom Filter Limitations
• User or operator impact: Trade-offs & Failure Modes: Bloom Filter Limitations