bloom filters #

A Bloom filter is a space-efficient representation of a set for answering membership queries. It deliberately gives asymmetric answers:

• definitely absent — at least one required bit is zero;
• possibly present — every required bit is one.

The second answer can be a false positive. The first is exact, provided bits are never cleared, the hash scheme does not change, and the filter has not been reset. A Bloom filter cannot return the stored keys, attach values to them, or prove that a positive result corresponds to a particular insertion.

structure and operations #

A filter has an array of m bits and k hash-derived positions per key. It starts all-zero. Insertion sets all k positions; lookup tests the same positions.

A twelve-bit array has positions two, seven, eight, and eleven set. One query maps only to set bits and is possibly present. Another maps to a zero bit and is definitely absent. bit array after several insertions 001000011001 01234567891011 query A→ {2, 7, 11}all one → possibly present query B→ {2, 5, 11}bit 5 is zero → definitely absent

In pseudocode:

insert(x):
    for i in 0..k: bits[position(x, i)] = 1

contains(x):
    for i in 0..k:
        if bits[position(x, i)] == 0: return definitely_absent
    return possibly_present

Insertion and lookup are O(k) and the representation occupies exactly m bits, independent of key size. Re-inserting a key changes nothing except any external item counter: the bit array represents a set, not a multiset.

false-positive probability #

Assume the k positions are independent and uniformly distributed. After inserting n keys, the probability that a particular bit remains zero is

P(bit = 0) = (1 - 1/m)^(kn) ≈ e^(-kn/m)

A query for an absent key is a false positive when all k tested bits are one:

p ≈ (1 - e^(-kn/m))^k

For fixed m and n, the minimizing number of probes is

k_opt = (m/n) ln 2

so an optimally filled filter has about half its bits set. Solving for a target false-positive rate gives

bits per key = m/n = -ln(p) / (ln 2)^2

target p	bits per key	optimal k
1%	9.59	6.64 → 7
0.1%	14.38	9.97 → 10
0.01%	19.17	13.29 → 13

These are design estimates, not guarantees. Weak or correlated hashes, nonuniform reduction into the bit range, uncertain cardinality, and concurrent publication bugs can all make the realized rate worse.

capacity is part of the type #

A fixed Bloom filter is really parameterized by (expected n, target p), not only by its byte length. Continuing past the expected cardinality increases bit occupancy and the false-positive rate rapidly; the filter still has no false negatives, but it may stop being useful.

Occupancy is therefore a useful runtime measurement. If X is the observed fraction of one-bits, the inserted cardinality can be estimated as

n_est ≈ -(m/k) ln(1 - X)

Track occupancy or estimated cardinality rather than trusting an insertion counter, which may count duplicate keys. Rebuild, rotate, or add another filter before saturation.

deriving the positions #

Computing k unrelated hashes is usually unnecessary. Double hashing derives all positions from two independent-looking hash values:

position(x, i) = (h1(x) + i h2(x)) mod m

Kirsch and Mitzenmacher showed that this has the same asymptotic false-positive behavior as independent hashes. In implementations, the details still matter:

• use a hash with adequate avalanche behavior for the actual key distribution;
• use wrapping arithmetic intentionally;
• map to [0, m) without avoidable modulo bias;
• persist the hash algorithm, seed, m, and k with serialized filters;
• publish inserted bits before readers rely on the corresponding data.

A filter is not independently authoritative. It is a fast negative gate in front of a slower exact lookup.

deletion changes the contract #

Clearing a bit during deletion is invalid because other keys may share it. It can create false negatives for keys that remain in the set.

A counting Bloom filter replaces each bit with a small counter: insertion increments and deletion decrements the selected counters. This permits deletion when increments and decrements are balanced, at a substantial space cost and with counter-overflow concerns. If approximate expiry is acceptable, rotating whole immutable filters is often simpler than deleting individual keys.

locality and common variants #

The classical layout scatters k probes over the whole bit array. Once the array is larger than cache, memory latency can dominate hashing.

• blocked Bloom filter: one hash chooses a cache-line-sized block and the remaining probes stay inside it. A query usually fetches one cache line, at the cost of a somewhat higher false-positive rate because inserts are unevenly distributed among blocks.
• partitioned Bloom filter: split the bit array into k regions and place one probe in each. This regularizes placement and can simplify parallel or hardware implementations.
• scalable Bloom filter: add progressively sized filters as cardinality grows. Queries check every generation, trading lookup work for growth without a fixed final capacity.
• stable Bloom filter: age bits or counters continuously to represent a moving window. Expiry introduces false negatives, so this is a different contract from the classical structure.

Cuckoo filters, quotient filters, ribbon filters, and XOR filters solve nearby membership problems with different build, update, deletion, and locality tradeoffs. They are alternatives, not Bloom-filter variants merely because they are probabilistic.

when it fits #

A Bloom filter earns its space when negative results avoid work that is much more expensive than probing a few bits: disk or object reads, decompression, network requests, or exact set lookups. It is a poor fit when most queries are positive, false positives are unacceptable without an exact fallback, keys must be enumerated, or the population cannot be bounded or rotated.

The economic question is not whether the filter is small. It is whether

negative-query rate × avoided cost > filter lookup cost + false-positive cost

sources #

• Burton H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,” Communications of the ACM 13(7), 1970, doi:10.1145/362686.362692.
• Andrei Broder and Michael Mitzenmacher, “Network Applications of Bloom Filters: A Survey,” Internet Mathematics 1(4), 2004, doi:10.1080/15427951.2004.10129096.
• Adam Kirsch and Michael Mitzenmacher, “Less Hashing, Same Performance: Building a Better Bloom Filter,” ESA 2006, doi:10.1007/11841036_42.
• Felix Putze, Peter Sanders, and Johannes Singler, “Cache-, Hash- and Space-Efficient Bloom Filters,” WEA 2007, doi:10.1007/978-3-540-72845-0_9.