Bloom Filters and Probabilistic Set Membership
A Bloom filter is a compact data structure that answers the question “might this value be in a set?” using a bit array and several hash functions. It can say “definitely not present” or “possibly present,” but it cannot prove presence.
That trade-off makes Bloom filters useful when memory is limited and an occasional extra lookup is cheaper than storing or querying the full set.
The problem a Bloom filter solves
Suppose a service receives a request containing an identifier and needs to check whether that identifier is known. The straightforward solution is to store every identifier in a database, hash table, or in-memory set. Each lookup can then return an exact answer.
But an exact set can be expensive. The values themselves take space, and a remote database lookup adds latency and load. Sometimes the application mostly wants to reject values that are certainly unknown, while only occasionally checking a slower authoritative store.
A Bloom filter provides a cheap first check. It uses much less memory than storing the original values, at the cost of sometimes reporting that an unknown value might be present. The application must treat that result as a hint, not as proof.
A Bloom filter is best understood as a fast negative filter: it reliably rules values out, but it cannot reliably confirm them.
The representation: bits, not values
The filter starts with a fixed-size bit array: a sequence of bits, each initially set to 0. Unlike a normal set, it does not retain the inserted values. It retains only patterns of bits derived from them.
A hash function maps an input to a seemingly well-distributed number. The filter uses k hash functions, where k is a chosen count. Each hash selects one position in the bit array.
To insert a value such as user-123:
- Hash the value with each of the
kfunctions. - Convert each result into an array position, usually by taking its value modulo the array size.
- Set every selected bit to
1.
If the hashes select positions 4, 19, and 72, those three bits become 1. Inserting another value sets its own selected positions, while leaving already-set bits at 1.
The filter therefore stores no direct record saying which value caused which bit to be set. Different values can select some of the same positions. This overlap is called a collision.
Checking membership
To query a value, the filter hashes it with the same k functions and inspects the same k positions.
- If any selected bit is
0, the value was not inserted into this filter. The answer is definitely not present. - If all selected bits are
1, the value might have been inserted. The answer is possibly present.
The second result is uncertain because other inserted values may have set all those bits. For example, one value might set positions 4 and 19, while several other values set position 72. A query for a value that was never inserted can still find all three bits already set.
That is a false positive: the filter says “possibly present,” and the authoritative set says “absent.” It is not a failure for the filter to return this result; uncertainty is part of its design.
A standard Bloom filter does not produce false negatives. An inserted value sets all of its positions to 1, and inserting other values never changes a bit back to 0. When the value is queried later, all of its positions will therefore still be set—assuming the filter has not been corrupted and the query uses the same hashing rules.
A filter that says “definitely not present” can thus safely skip a database lookup. A filter that says “possibly present” should normally continue to the database or another exact check.
Size and hash count control accuracy
Two configuration choices determine most of a Bloom filter’s behavior:
m: the number of bits in the arrayk: the number of hash functions used per value
The expected false-positive probability depends on both choices and on n, the number of inserted values. A commonly used approximation is:
p ≈ (1 - e^(-kn/m))^k
Here, e is the base of natural logarithms. You do not need to calculate this during every lookup; the formula explains the trade-offs.
A larger bit array reduces false positives. With more positions available, inserted values overlap less often. The memory cost increases roughly in proportion to m.
More hash functions initially improve accuracy. Each additional hash gives a query another bit that must be set before the filter can report “possibly present.” But too many hashes also set more bits during insertion, eventually filling the array and increasing collisions. Hashing also costs more CPU time.
For a fixed array size and expected item count, the approximate hash count that minimizes false positives is:
k ≈ (m / n) ln(2)
In practice, choose the expected number of items and an acceptable false-positive rate first, then size the array and derive a modest k. The filter does not become more accurate merely because it has more hashes if the array is already too small.
What this looks like in a system
You may encounter a Bloom filter in a cache, storage engine, crawler, or request path as a configuration such as “bits per key” or “number of probes.” A log message about a filter “miss” often means the filter found a zero bit and avoided a more expensive lookup. A “hit” may only mean that the next lookup is worth attempting.
Standard Bloom filters also do not support ordinary deletion: clearing a bit could remove evidence needed by another value. Variants such as counting Bloom filters address that case with extra storage, but the basic mechanism remains the same.
The central rule is simple: a zero bit among the queried positions proves absence; all ones establish only possibility. That one-sided certainty is what lets Bloom filters save memory and avoid many unnecessary lookups without incorrectly discarding a value that is actually in the set.