Bloom Filter

Also Known As

TL;DR

Explanation

A Bloom filter uses multiple hash functions to set bits in a bit array. To test membership, all hash positions are checked — if any is 0, the element is definitely not in the set. If all are 1, the element is probably in the set (possible false positive). Bloom filters never produce false negatives. They are ideal for cache miss pre-screening, username availability checks, and preventing unnecessary database lookups.

Diagram

flowchart LR
    ADD[Add item X] --> HASH[Hash with k functions<br/>h1 h2 h3]
    HASH --> SET[Set bits in bit array<br/>positions 2, 7, 14]
    CHECK[Check item Y] --> HASH2[Hash with same k functions]
    HASH2 --> BITS{All bits set?}
    BITS -->|yes| MAYBE[Probably in set<br/>false positive possible]
    BITS -->|no| DEFNO[Definitely NOT in set<br/>no false negatives]
    INFO[Use case: cache negative lookups<br/>block known-bad passwords<br/>deduplicate crawl URLs]
style DEFNO fill:#238636,color:#fff
style MAYBE fill:#d29922,color:#fff
style INFO fill:#1f6feb,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Not accounting for false positive rate when sizing the bit array — too small a filter has high false positive rates.
• Trying to delete elements from a standard Bloom filter — use a Counting Bloom Filter for deletion support.
• Using a Bloom filter without a fallback — false positives require a definitive check against the source.
• Not understanding that Bloom filters are write-only for membership — you cannot enumerate members.

Code Examples

// Without bloom filter — every cache miss hits the DB:
function getUser(int $id): ?User {
    $cached = $cache->get("user:$id");
    if (!$cached) {
        return $db->find($id); // DB hit even for non-existent IDs
    }
    return $cached;
}

// Bloom filter pre-screens — DB only queried if probably exists:
function getUser(int $id): ?User {
    if (!$bloomFilter->mightContain("user:$id")) return null; // Definite miss
    $cached = $cache->get("user:$id");
    if (!$cached) {
        $user = $db->find($id); // Only if bloom says 'probably exists'
        if ($user) $cache->set("user:$id", $user);
        return $user;
    }
    return $cached;
}

References

• ↗ https://en.wikipedia.org/wiki/Bloom_filter

Tags

Related Terms