How it works
Start with an array of m bits, all zero, and k hash functions that map keys to positions in that array. The filter stores bits, not the original keys or their values.
To insert a key, compute its k positions and set those bits to 1. For example, if a URL maps to positions 2, 7, and 11, set those three bits; other URLs may share some of them.
To test membership, compute the same positions. If any bit is 0, the key is definitely absent from the inserted set. If every bit is 1, it might be present: unrelated keys may have collectively set those bits, creating a false positive.
Size the filter using the expected number of distinct keys n and target false-positive probability p: m ≈ -n × ln(p) / (ln(2))² bits, with k ≈ (m/n) × ln(2). A 1% target needs about 9.6 bits per key and 7 hash positions, assuming suitable hashing and the planned capacity.
Put the filter before an expensive membership lookup. In an LSM-tree storage engine, a filter for each immutable sorted table can rule out tables that do not contain a key, avoiding unnecessary disk reads. A positive result means search that table, not return a value.
The no-false-negative guarantee applies to keys successfully inserted into that filter, not automatically to everything in an external database. For mutable data, coordinate publication and updates so readers never trust an incomplete filter; during rebuilds, lag, or uncertainty, bypass it and query the authoritative store.
A worked example
Prefiltering a crawler's discovered URLs
Suppose a crawler expects 100 million distinct discovered URLs. At a 1% false-positive target, its Bloom filter needs about 960 million bits, or 120 MB, with roughly 7 hash positions per URL. For 1 million checks of genuinely new URLs, about 10,000 are expected to return “might exist” and require an exact membership read. The remaining checks can skip that read. A negative result still leads to an atomic insert-if-absent in the durable URL frontier, because two workers may discover the same URL concurrently. Positive results are verified before discarding a URL. Filter updates must cover published discoveries before readers trust negatives; otherwise, workers bypass the filter.
Trade-offs to say out loud
- Memory versus false positives
- A lower false-positive target uses more memory but reduces unnecessary downstream lookups.
- Lookup savings versus CPU cost
- Hashing and bit accesses add work to every check, so the filter pays off most when absent-key lookups are common and expensive.
- Capacity must be planned
- Inserting substantially more keys than expected raises the false-positive rate, requiring a rebuild or additional filter layers.
- No ordinary deletion
- Clearing a bit can break membership checks for other keys, so deletion requires a rebuild or a suitable alternative such as a counting Bloom filter.
- Synchronization becomes a correctness concern
- A stale or partially built filter can incorrectly reject keys that exist in the backing store unless reads fall back safely.
- Membership is not an atomic claim
- Even a negative result cannot prevent concurrent workers from inserting the same key, so uniqueness still requires an authoritative atomic operation.
When to reach for it
- A read path spends substantial disk or network work checking keys that usually do not exist.
- An LSM-tree key-value store needs to avoid probing many sorted tables for each lookup.
- A web crawler tracks a very large set of discovered URLs and needs a compact membership prefilter.
- A discovery service checks candidates against large seen-item or exclusion histories, with exact verification when false exclusions are unacceptable.
How to bring it up in the interview
- Start with the expensive operation and expected absent-key fraction rather than proposing a Bloom filter by default; interviewers may ask whether a negative cache or exact in-memory set would be simpler.
- State the contract explicitly: negative means absent from the inserted set, positive means verify; explain what a false positive would do to the product.
- Estimate distinct-key count, memory, and a target false-positive rate, then explain how growth changes those assumptions.
- Separate the filter optimization from correctness: describe authoritative lookups, atomic deduplication, and safe behavior while filters are stale or rebuilding.
- Be ready to discuss deletion and lifecycle: immutable-table filters can be rebuilt during compaction, while mutable sets need a deliberate update and expiration strategy.
Common mistakes
- Treating a positive result as proof that a key exists, which can silently drop new URLs or hide eligible recommendations.
- Claiming there can never be false negatives without checking whether the filter includes every relevant committed write.
- Clearing bits to delete individual keys from a standard Bloom filter.
- Using a filter as the sole idempotency or uniqueness mechanism for payments, billing events, or concurrent work claims.
- Choosing a false-positive rate without estimating capacity, absent-key traffic, or the cost of the remaining lookups.
Where it comes up
Interview questions where bloom filters is part of a strong answer, and why.
- Design a web crawlerLarge-scale URL deduplication needs compact membership checks, an explicit false-positive policy, and atomic frontier insertion.
- Design a distributed key-value storeAn LSM-tree storage-engine design uses Bloom filters to avoid unnecessary sorted-table reads for absent keys.
- Design a dating app like TinderLarge seen-profile and exclusion histories can use Bloom prefilters, with exact confirmation to avoid falsely excluding eligible profiles.
Questions people ask
Can a Bloom filter have false negatives?
A correctly maintained standard Bloom filter has no false negatives for successfully inserted keys, provided bits are not cleared. An application can still incorrectly reject existing database keys if its filter is stale, incompletely rebuilt, or missing updates.
How much memory does a Bloom filter use?
Memory depends on the number of distinct keys and the target false-positive probability. A 1% target takes about 9.6 bits per key, while a 0.1% target takes about 14.4 bits per key, excluding implementation overhead. These estimates assume suitable hashing and that the filter stays near its planned capacity.
What is the difference between a Bloom filter and a cache?
A cache typically stores keys and values so it can answer requests directly. A Bloom filter stores an approximate membership summary and cannot return the associated value. It can complement a cache by screening nonexistent keys before they reach the backing database, provided its coverage is kept correct.