Bloom Filter

What it is

A Bloom filter is a compact probabilistic data structure for membership tests. It can say an item is definitely not present or maybe present.

Why it matters

It saves expensive lookups when most checks are misses. Systems use Bloom filters before hitting databases, caches, indexes, storage, or network services.

How it works

Multiple hash functions map an item to bit positions. To add an item, set those bits. To check an item, verify all bits are set. If any bit is missing, the item is definitely absent.

# state: bits[m]  (all initialized to 0)
# config: k hash functions, m bits

function add(item):
    for i in 1..k:
        pos = hash_i(item) % m
        bits[pos] = 1

function might_contain(item):
    for i in 1..k:
        pos = hash_i(item) % m
        if bits[pos] == 0:
            return False          # definitely absent
    return True                   # maybe present (false positive possible)

add only sets bits — it never clears them, which is why deletion is not supported. might_contain can only return false negatives-free: a False is always correct, a True might be wrong.

Checking membership reads the same bit positions. If all are set, the item is maybe present (false positives possible). If any bit is 0, the item is definitely absent.

Loading diagram...

When to use it

Use it for negative cache checks, deduplication hints, database read avoidance, crawler filters, and log or storage membership tests.

Tradeoffs / failure modes

Bloom filters allow false positives and usually do not support deletion without variants like counting Bloom filters. The false-positive rate depends on the number of hash functions, bit array size, and number of items inserted.

Tiny example

Before querying a cold database partition, a service checks a Bloom filter and skips the query when the key is definitely absent.

Related guides and systems

See Caching Strategies, Full-Text Search, Rate Limiting, Gmail, GitHub, Google Maps, and Airbnb.