Where do a bloom filter's false positives come from, given that it stores only bits?

middlemust knowfreq 58%

answer

no key is ever written down
a query checks several positions at once
the array records what, never who
different elements can cover all k positions
the union of set bits, not one collision

basics

~20 s

False positives come from the union of everything already inserted. A never-added element tests positive when all of the positions it checks happen to be set — each possibly by a different element. No two keys need to share a hash value.

solid answer

~50 s

Insertion sets k bits chosen by k hash functions; a query recomputes the same k positions and reports absence the moment it sees a zero. Because a bit records only that someone set it, never who, a query is really testing the element against the union of every insertion so far. So a false positive needs no hash collision at all: each of the k positions can have been set by a different, unrelated key, and the query sees all ones. That reframes the two knobs. More bits (m) lowers density and helps monotonically. More hash functions (k) requires more independent coincidences per query, which helps — but each insertion now sets k bits, so the array saturates faster, and past an optimum the rate rises again. Query cost is k probes regardless of how many elements the filter holds.

Insertion sets `k` bits chosen by `k` hash functions; a query recomputes the same `k` positions and reports absence the moment it sees a zero. Because a bit records only that *someone* set it, never *who*, a query is really testing the element against the union of every insertion so far. So a false positive needs no hash collision at all: each of the `k` positions can have been set by a different, unrelated key, and the query sees all ones. That reframes the two knobs. More bits (`m`) lowers density and helps monotonically. More hash functions (`k`) requires more independent coincidences per query, which helps — but each insertion now sets `k` bits, so the array saturates faster, and past an optimum the rate rises again. Query cost is `k` probes regardless of how many elements the filter holds.

code

pseudocode · 12 lines

pseudocode

// B is an m-bit array, initially all zeros
// h_1 .. h_k are k independent hash functions

insert(x):
    for i in 1..k:
        B[h_i(x) mod m] = 1

contains(x):
    for i in 1..k:
        if B[h_i(x) mod m] == 0:
            return DEFINITELY_ABSENT
    return MAYBE_PRESENT

go deeper

for a junior

Remember the shape: a bit array plus several hash functions, with no keys stored anywhere. A lookup checks a fixed handful of positions and can stop at the first zero it finds.

for a middle

Walk the insert and query paths out loud and say precisely why a never-added key can test positive: its positions were set by other keys. Add that a query costs the same fixed number of probes no matter how many elements the filter holds.

for a senior

Reason about the error curve rather than quoting a formula: bits always help, hash count helps only up to an optimum, and load is what silently degrades a live filter. Tie that to how you would monitor one sitting in front of an expensive lookup.

for a principal

Frame the mechanism as a budget. Bits per element buy an error rate, every extra hash function spends those bits faster, and the right target comes from what a wasted authoritative lookup costs you at full traffic.

The two paths, precisely

The structure is an m-bit array plus k hash functions. Insertion computes k positions from the element and sets each to 1. A query computes the same k positions and scans them; the first zero it finds ends the query with a definite 'not present', and if all k are ones it returns 'possibly present'. Both operations touch exactly k positions, so both are constant-time in the number of stored elements — a filter holding a billion keys probes the same handful of positions as one holding a thousand.

The bit has no owner

Everything interesting follows from one fact: a set bit records that some element mapped there, not which one. The array is therefore not a collection of per-element records; it is a single superimposed union of every insertion. When you query a key that was never added, you are not asking 'is this key here?' — you are asking 'does the union already cover all k of this key's positions?'. Those are different questions, and the second says yes more often than the first.

This is the misconception the question aims at. Candidates usually say false positives happen 'when two keys hash to the same value'. Hash collisions do exist and do contribute, but they are not required. With k = 3, a stranger's three positions can be covered by three completely different keys inserted at three different times, none of which collides with it or with each other on any single hash function. The failure is a covering failure, not a collision failure. That distinction is why the error rate depends on how full the array is, and not on any pairwise property of the keys.

Where this bites in practice

A storage engine that keeps a bloom filter per on-disk data file uses it to answer 'could this key be in this file?' before paying for a disk read. Most keys were never written to most files, so the overwhelming majority of queries return a definite no and the read is skipped — that is the entire win, and it is powered purely by the exact negative. A false positive costs one wasted read: the engine goes to disk, finds nothing, and moves on. Nothing is incorrect, only slower. That is the shape of workload the structure is built for, and it explains why the rate is chosen by weighing wasted work rather than correctness.

The two knobs, and why one is not monotone

Let n be the number of elements inserted. After n insertions of k bits each, the fraction of the array still zero is about e^(-kn/m), so the chance that all k positions of a stranger are set is roughly (1 - e^(-kn/m))^k.

More bits, fixed k and n: density falls, the rate falls. Memory always buys accuracy.
More hash functions, fixed m and n: two opposing effects. A query now demands k independent coincidences, which pushes the rate down; but each insertion sets k bits, so the array fills faster, which pushes it up. The result is a minimum, not a slope: the rate falls as k grows, bottoms out near k = (m/n) * ln 2, and rises after that. A filter with far too many hash functions is worse than one with a sensible handful, which surprises people who assume more hashing is always safer.
More elements, fixed m and k: the rate rises, and steeply once the array is past roughly half set. Nothing warns you; the queries still return, just positive more often.

Change	Effect on false-positive rate
Increase bits `m`	Falls, monotonically
Increase hash count `k`	Falls, then rises past an optimum
Insert more elements `n`	Rises, steeply once dense
Increase query volume	No effect at all

That last row is worth saying out loud in an interview: the error rate is a property of what has been inserted, not of how often you ask. The same query gives the same answer forever until the filter is rebuilt.

Why the memory argument is so strong

Because only hash outputs index the array, the cost per element is a number of bits that does not depend on the element's size. A two-hundred-character address and an eight-byte identifier each set k bits. An exact set must store the key material itself plus per-entry structural overhead, so its footprint grows with both the count and the length of what you store. The filter's footprint grows only with the count. For huge sets of long keys the difference is an order of magnitude or more, and that is the reason to accept a one-sided error at all.

## The two paths, precisely The structure is an `m`-bit array plus `k` hash functions. Insertion computes `k` positions from the element and sets each to 1. A query computes the same `k` positions and scans them; the first zero it finds ends the query with a definite 'not present', and if all `k` are ones it returns 'possibly present'. Both operations touch exactly `k` positions, so both are constant-time in the number of stored elements — a filter holding a billion keys probes the same handful of positions as one holding a thousand. ## The bit has no owner Everything interesting follows from one fact: a set bit records that some element mapped there, not which one. The array is therefore not a collection of per-element records; it is a single superimposed union of every insertion. When you query a key that was never added, you are not asking 'is this key here?' — you are asking 'does the union already cover all `k` of this key's positions?'. Those are different questions, and the second says yes more often than the first. This is the misconception the question aims at. Candidates usually say false positives happen 'when two keys hash to the same value'. Hash collisions do exist and do contribute, but they are not required. With `k = 3`, a stranger's three positions can be covered by three completely different keys inserted at three different times, none of which collides with it or with each other on any single hash function. The failure is a *covering* failure, not a *collision* failure. That distinction is why the error rate depends on how full the array is, and not on any pairwise property of the keys. ## Where this bites in practice A storage engine that keeps a bloom filter per on-disk data file uses it to answer 'could this key be in this file?' before paying for a disk read. Most keys were never written to most files, so the overwhelming majority of queries return a definite no and the read is skipped — that is the entire win, and it is powered purely by the exact negative. A false positive costs one wasted read: the engine goes to disk, finds nothing, and moves on. Nothing is incorrect, only slower. That is the shape of workload the structure is built for, and it explains why the rate is chosen by weighing wasted work rather than correctness. ## The two knobs, and why one is not monotone Let `n` be the number of elements inserted. After `n` insertions of `k` bits each, the fraction of the array still zero is about `e^(-kn/m)`, so the chance that all `k` positions of a stranger are set is roughly `(1 - e^(-kn/m))^k`. - **More bits, fixed `k` and `n`:** density falls, the rate falls. Memory always buys accuracy. - **More hash functions, fixed `m` and `n`:** two opposing effects. A query now demands `k` independent coincidences, which pushes the rate down; but each insertion sets `k` bits, so the array fills faster, which pushes it up. The result is a minimum, not a slope: the rate falls as `k` grows, bottoms out near `k = (m/n) * ln 2`, and rises after that. A filter with far too many hash functions is worse than one with a sensible handful, which surprises people who assume more hashing is always safer. - **More elements, fixed `m` and `k`:** the rate rises, and steeply once the array is past roughly half set. Nothing warns you; the queries still return, just positive more often. | Change | Effect on false-positive rate | | --- | --- | | Increase bits `m` | Falls, monotonically | | Increase hash count `k` | Falls, then rises past an optimum | | Insert more elements `n` | Rises, steeply once dense | | Increase query volume | No effect at all | That last row is worth saying out loud in an interview: the error rate is a property of what has been *inserted*, not of how often you *ask*. The same query gives the same answer forever until the filter is rebuilt. ## Why the memory argument is so strong Because only hash outputs index the array, the cost per element is a number of bits that does not depend on the element's size. A two-hundred-character address and an eight-byte identifier each set `k` bits. An exact set must store the key material itself plus per-entry structural overhead, so its footprint grows with both the count and the length of what you store. The filter's footprint grows only with the count. For huge sets of long keys the difference is an order of magnitude or more, and that is the reason to accept a one-sided error at all.

Does a false positive require two keys to hash to the same value?
No. Each of the positions a stranger checks can have been set by a different, unrelated insertion. Because a bit records no ownership, the query really tests the key against the union of everything inserted. Collisions on individual hash functions make coverage likelier, but the structure produces false positives without any of them.
With the bit array fixed, what happens to the error rate as the hash count keeps growing?
It falls at first, because a positive now needs more independent coincidences, then rises, because every insertion sets that many more bits and the array saturates sooner. The minimum sits near `(m/n) * ln 2` hash functions. More hashing is not monotonically safer, which is the counterintuitive part.
Does query volume affect the false-positive rate?
No. The rate is determined by how densely the array is set, which depends only on the number of elements inserted and the parameters. Querying never modifies the array, and the same key always gets the same answer until the filter is rebuilt — a false positive is permanent, not a random per-call event.

saying these in an interview costs you the question

Claims the filter stores hashed copies of the keys
Says a false positive requires two keys with equal hashes
Believes more hash functions always lower the error rate
Thinks a query must scan the whole bit array
Assumes lookup cost grows with the number of inserted elements

Where do a bloom filter's false positives come from, given that it stores only bits?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The two paths, precisely

The bit has no owner

Where this bites in practice

The two knobs, and why one is not monotone

Why the memory argument is so strong

▾common follow-ups3 questions

▾red flags5 flags

§ context

▾related questions5 questions

▾related topics3 topics

The two paths, precisely

The bit has no owner

Where this bites in practice

The two knobs, and why one is not monotone

Why the memory argument is so strong

answer

go deeper

context