Skip to main content

Bloom Filters

A Bloom filter answers one narrow question extremely cheaply: "is this element possibly in the set, or definitely not?" It's a probabilistic data structure — it can return a false positive (say "maybe" for something that isn't actually there), but it can never return a false negative (if it says "definitely not," that's always correct). That one-directional guarantee, traded for a tiny, fixed amount of memory regardless of how large the underlying set is, is what makes it useful.

How it works​

A Bloom filter is a fixed-size bit array, initially all zeros, plus several independent hash functions. Adding an element hashes it with each function and sets the resulting bit positions to 1. Checking membership hashes the candidate the same way and checks whether all of those positions are set — if even one is still 0, the element was definitely never added; if all are 1, it probably was, but different elements can coincidentally set the same bits, which is exactly where false positives come from.

System Design Lab

More hash functions and a bigger bit array reduce the false-positive rate, at the cost of more memory and more hashing work per check — a tunable tradeoff chosen upfront based on how many elements the filter needs to hold and how low a false-positive rate the use case can tolerate.

Why "definitely not" is the useful guarantee​

The whole point of a Bloom filter is using its cheap, constant-size "definitely not" answer to skip an expensive operation — a disk read, a network call, a full database query — the vast majority of the time it isn't needed, while accepting an occasional unnecessary check on the rare false positive. This is the same underlying trade as Checksums: both give up perfect certainty for a large, deliberate gain in speed or space, and both are correct to reach for exactly when the cost of the rare error is small compared to the cost of doing the expensive thing every single time.

Where it shows up in real systems​

  • Avoiding unnecessary database or disk lookups — a cache or database can keep a Bloom filter of every key it holds; before doing an expensive disk read for a key that might not exist, it checks the filter first. LSM-tree storage engines (used by Cassandra, HBase, and others) use exactly this to avoid checking every on-disk file for a key that isn't there.
  • Web crawlers — checking whether a URL has already been visited, without storing every URL ever seen in full (see Design a Web Crawler for this applied at billion-URL scale).
  • Network routers and CDNs — quickly checking whether content might be cached nearby before making a network round trip.
  • Malicious URL / password-breach checks — services like "has this password been in a known breach" use a Bloom filter (or similar structure) to avoid a full database query for the overwhelming majority of checks that come back negative.

The tradeoff to name explicitly​

A Bloom filter can only ever be used to rule things out cheaply — it can never be the sole source of truth for "yes, this exists," because a positive result still needs to be confirmed against the real data. It also can't remove elements in its basic form (unsetting a bit could break membership checks for a different element that happens to share that bit), and its false-positive rate creeps up as more elements are added beyond what it was sized for, which means capacity planning matters upfront.

Why this matters in an interview​

Naming a Bloom filter is a strong, specific answer whenever a design needs to cheaply avoid expensive lookups for things that mostly don't exist — "before hitting the database, check a Bloom filter of known keys" is a concrete, memory-efficient optimization that shows familiarity with probabilistic data structures beyond the basics.

Using a Bloom filter to skip expensive lookups: pros and cons​

Pros

  • Constant, tiny memory footprint regardless of how large the underlying set is
  • Extremely fast O(k) membership checks (k = number of hash functions)
  • Never a false negative — a "definitely not" answer can always be trusted

Cons

  • Can return false positives, so a positive still needs real confirmation
  • Can't enumerate or retrieve the elements it holds — only test membership
  • Standard form doesn't support deletion without extra structure (e.g. a counting Bloom filter)

Further Reading​

Saved locally in your browser — visible in the sidebar as you go.