A compact preliminary question
Suppose a large archive is expensive to search. Before reading it, we would like a small in-memory structure to answer: “Could this key be present?” A Bloom filter trades exact negative answers for possible false positives. It is useful only as a preliminary test: a “possibly present” answer must still be checked against an authoritative store when exact membership matters.
Definition 16.1.1
(Bloom filter)
Choose integers and . A Bloom filter is an array of bits, initially zero, together with hash functions taking values in . To insert a key , set every bit at to one. To query , return “possibly present” if all addressed bits are one; otherwise return “absent”. A false positive is a “possibly present” answer for a key that was never inserted.
Hash collisions, including repeated addresses for one key, are allowed. Insertion is idempotent: inserting a key again changes no bits if its hashes are fixed.
Proposition 16.1.2
(One-sided correctness)
If a key was inserted and no bit has subsequently been cleared, the query procedure cannot report it absent. This statement is deterministic; it needs no random hash assumption.
Proof
(Bits are only ever set)
At insertion, every bit addressed by the key is set to one. Later insertions only set bits, so those bits remain one at query time. The query therefore reports “possibly present”. The argument includes collisions and repeated insertions. It assumes the same hash functions and bit array are used at insertion and query, and that updates are not lost. It does not make the positive answer exact.
The converse, that a positive answer certifies membership, is false.
Counterexample mode
A positive answer need not be membership
With and , insert with . If a different key also hashes to 1, querying reports “possibly present” even though was never inserted. A filter cannot distinguish these two histories from that bit alone.
A precise random model
Definition 16.1.3
(Ideal hash model for a fixed query)
Fix a set of distinct inserted keys and a query key not in that set, before the hashes are chosen. In the ideal hash model, the hash values of these keys are mutually independent and each is uniformly distributed over the bit positions.
This ideal model is stronger than merely requiring each hash value to be uniform; deterministic implementations need separate evidence that their hash choices give a suitable approximation for their workload. The result does not automatically cover a query chosen adaptively after observing the filter.
Let be the number of one bits after insertion.
Proposition 16.1.4
(Occupancy and false-positive probability)
Under the ideal hash model,
where is the probability that the fixed query key is reported “possibly present”.
Proof
(Linearity for the occupancy, conditioning for the query)
There are independent insertion addresses. Each position is untouched with probability ; summing the indicators of the positions being touched and using linearity of expectation gives . Conditioned on the completed filter, the absent query's addresses remain independent uniform draws, because they are independent of the insertion addresses. Each hits a one bit with conditional probability , so the conditional false-positive probability is . Averaging over the filter gives . These formulas also cover : with , and the false-positive probability is zero.
Proof X-ray
Two independence claims of different strength
The proof uses independence twice, and the two uses must not be merged. First, the query's addresses are independent of the insertion addresses; this is where the query key must be fixed in advance and distinct from every inserted key. A query chosen after looking at the filter, or an inserted key queried again, breaks it. Second, given the filter, the query addresses are independent of each other, which yields the product . They are not independent unconditionally: every one of them succeeds more often when is large, so the events share the random occupancy. That is why the th power is taken before the average. The deterministic no-false-negative proposition uses neither claim.
The random hash model is needed for the probability claim, not for the deterministic no-false-negative proposition.
An exact finite-size formula and a safe bound
For , count insertion-address sequences that occupy exactly positions: first choose those positions, then count sequences in which every chosen position occurs at least once.
Proposition 16.1.5
(Exact finite-size distribution of the occupancy)
Under the ideal hash model, put and use the convention . For ,
Proof
(Inclusion–exclusion over omitted positions)
There are equally likely address sequences. For a fixed set of positions, start with all sequences using those positions. Subtract those omitting a specified position, add those omitting two, and continue by inclusion–exclusion. Multiplication by chooses the occupied set uniquely. Finally condition on and sum the conditional probabilities. For , the convention makes only have probability one. This formula is exact, although alternating terms can make direct floating-point evaluation numerically unstable.
Concept lensCombinatorial
Occupancy as counting surjections
An address sequence of length that occupies exactly a chosen set of positions is a surjection from the addresses onto those positions. Such a surjection is a partition of the addresses into nonempty blocks, followed by an assignment of the blocks to the positions, so the inclusion–exclusion sum equals , where is a Stirling number of the second kind. Thus . For and this gives and , as computed below.
Without computing the distribution, and imply the useful, potentially loose bounds
The first uses for ; the second holds for every realized filter. Neither claims that query-bit events are independent after averaging over the insertion randomness. The commonly used expression instead replaces random occupancy by its mean; it is a heuristic in this finite model, not the exact probability in general.
Worked example 16.1.6
(The small-filter correction)
Take , and one inserted key. Its two addresses coincide with probability , giving ; otherwise . An absent query therefore has false-positive probability
The mean occupancy fraction is , but its square is , not . The first safe bound gives and the second gives , so the sharper of them here is .
Worked example 16.1.7
(Evaluating the inclusion–exclusion formula)
Take , and one inserted key, so . The formula gives
and , as it must be, since two addresses cannot occupy three positions. The probabilities sum to one. Directly: the two addresses coincide with probability . Hence
For comparison, , so the mean-occupancy heuristic gives , below the exact . The safe bounds give and , both above it.
Worked example 16.1.8
(Two distinct keys versus one repeated key)
Let and . Insert two distinct fixed keys. Their addresses coincide with probability , so ; with probability , they differ and . A fixed absent key therefore has
By contrast, inserting the same key twice sets the same address twice: and the false-positive probability is . The count in the model means distinct inserted keys; it is not the number of insertion calls. Treating the repeated call as an independent new hash draw would change the algorithm and give the wrong calculation.
Common mistake
(Raising the mean occupancy to the kth power and calling it exact)
The expression replaces the random occupancy by its mean before taking the power. Since is convex on , Jensen's inequality gives : the heuristic can only underestimate the exact finite-model probability, with equality for . The examples above show the gap, against and against .
Merging, deletion and operational meaning
Two filters built with the same , and hash functions can be combined bit by bit using OR. Each output bit is one exactly when either input had it set, so this is exactly the bit array obtained by inserting the union of the two sets. This equality is deterministic even when the sets overlap. However, a probability calculation for the union still needs the hash assumptions for its distinct keys and the query. An OR of filters with different hash functions has no such membership interpretation.
Common mistake
(Deleting a key by clearing its bits)
A naive deletion that clears a key's bits is unsafe: a different inserted key may share one of those bits. For example, with both keys use the sole bit, so deleting either by clearing it makes the other appear absent. The one-sided correctness proposition assumed that no bit is ever cleared, and this is exactly the hypothesis the deletion violates.
A counting variant can maintain multiplicities, but safe deletion then requires a correct record of what was inserted, consistent counters, and no overflow or lost update. The ordinary bit array alone cannot recover these multiplicities.
A filter saves I/O only if the cost of its memory, hash computations, and false-positive lookups is justified by the workload. A high occupancy makes most queries positive. Also, if the input or query is adversarial and can exploit the chosen hashes, the fixed-query random guarantee is not a security guarantee. Record the hash family, seed policy, insertion count and measured workload separately from the ideal model.
Practice with solutions
Quick check
(Let , , and insert one key. Under the ideal model, find the false-positive probability for one fixed absent key.)
Count the one bits first.
Solution · Answer
Exactly one bit is set. The query hits it with probability . Equivalently deterministically and .
Quick check
(With , , insert one key and query a fixed absent key. Compute the probability that all four hash addresses are equal. Is it the entire false-positive probability?)
Separate the cases and .
Solution · Answer
The first address is arbitrary; each of the other three matches it with probability , so the probability is . It accounts for the branch only. If insertion fills both positions, every query is positive, contributing another ; the total is .
Quick check
(Two filters with identical parameters and hashes contain sets and . Explain why their OR gives the filter for , including when .)
Describe when a position is one after the OR.
Solution · Answer
A position is one after the OR precisely when at least one key from either set hashes to it. This is the insertion rule for the union. Duplicate insertions do not change a bit that is already one.
Quick check
(An engineer clears all bits belonging to a departing key. Give a concrete false negative and explain what extra state a counting approach needs.)
Use the smallest possible filter.
Solution · Answer
With , insert two different keys; both set the only bit. Clearing it for the first makes a query for the second return absent. Counters would need to retain the number of active contributions and be updated exactly, including handling repeated keys and overflow; the ordinary bit does not contain this information.
These calculations concern a fixed query in the finite ideal model. They are not a universal guarantee for real hash implementations, adaptive queries or arbitrary deletions.