Bloom Filters: Bit Arrays, Hash Probes, and False Positives

21 Oct 2026 algorithms

A Bloom filter is a compact, probabilistic data structure for testing whether a value may belong to a set. It can say “definitely not present” or “maybe present,” but it cannot safely say “definitely present.”

The problem Bloom filters solve

Suppose a service receives a request containing an object ID and needs to decide whether that ID exists in a large database. Looking up every ID in the database may be slow, expensive, or involve a network call. Keeping every ID in a normal set gives fast lookups, but the set can consume substantial memory.

A Bloom filter provides a much smaller first check. It can quickly reject values that the database cannot contain, avoiding many unnecessary lookups. Values that pass the filter still need an authoritative check.

You may encounter this in a cache, storage engine, database index, or configuration flag described as a “probabilistic membership check.” The filter is usually an optimization, not the source of truth.

The bit array

A Bloom filter starts with a fixed-size bit array: a sequence of bits, each initially set to 0. For example, a filter might contain one million bits. Unlike a normal set, it does not store the original values or even one distinct record for each value.

To add a value, the filter runs that value through several hash functions. A hash function deterministically maps an input to a number. Each resulting number is converted into an index within the bit array, and the bit at each index is changed from 0 to 1.

These indexes are called hash probes: the positions the operation examines or modifies. If a filter uses three hash probes for user-123, adding that value might set bits 17, 420, and 901 to 1.

The exact positions are not meaningful by themselves. They are just a compact fingerprint of the value. Different values can produce some of the same positions; this overlap is called a collision.

Adding and checking a value

Adding a value is straightforward:

Compute the filter’s configured hash probes for the value.
Set every selected bit to 1.

Checking a value performs the same probes but does not modify the array:

Compute the same positions.
Read every selected bit.
If any bit is 0, report “definitely not present.”
If all bits are 1, report “maybe present.”

The check works because adding a value always sets all of its required bits. Therefore, if one required bit is still 0, that value could not have been added to this filter.

The reverse conclusion is not safe. A value that was never added can still find all of its positions already set to 1 by other values. The filter cannot tell whether those bits were set by this value or by unrelated values.

A Bloom filter can produce false positives, but not false negatives—assuming it is queried consistently and bits are not accidentally cleared.

A false positive is the result “maybe present” for a value that is actually absent. It costs an unnecessary authoritative lookup, but it must not cause the application to treat the value as confirmed present. If a false positive would grant access, skip validation, or suppress required work, the Bloom filter is being used incorrectly.

Why the number of probes matters

Using only one hash probe means each inserted value sets only one bit. The filter fills slowly, but unrelated values have a relatively high chance of sharing that bit. More probes make each value’s fingerprint more distinctive: a random absent value must find several bits already set before it becomes a false positive.

However, every inserted value also sets more bits. With too many probes, the array fills rapidly. Once most bits are 1, almost every lookup finds all its probes set, and the false-positive rate rises again.

For a filter with m bits, n inserted values, and k hash probes, a commonly used approximation for the false-positive probability is:

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

Here, e is the base of the natural logarithm. The formula captures the trade-off:

Increasing m gives the values more space, so fewer unrelated probes collide and p decreases.
Increasing n puts more values into the same space, sets more bits, and increases p.
Increasing k initially decreases p, but eventually sets too many bits and makes p increase.

For fixed m and n, the approximate probe count that minimizes false positives is:

k ≈ (m/n) ln 2

At this optimum, the false-positive rate is approximately:

p ≈ (0.6185)^(m/n)

The ratio m/n—bits allocated per inserted value—is therefore a useful sizing measure. Roughly ten bits per inserted value, with a suitable probe count, produces a false-positive rate near one percent. That is an estimate, not a guarantee: real implementations depend on the hash construction, the number of inserted values, and how closely the input distribution matches the assumptions.

The operational boundary

A Bloom filter’s size and probe count must be chosen for the expected population, not merely the current one. If a filter designed for one million values receives five million, its bits become much denser and false positives become common.

Standard Bloom filters also do not support safe deletion. Clearing a bit for one value might clear a bit needed by other values. Variants such as counting Bloom filters use counters instead of single bits when deletion is required, but that changes the memory and behavior trade-offs.

The safe design pattern is simple: use the filter to avoid work, then use the database, cache, or other authoritative structure to confirm a possible match. The bit array makes rejection cheap; the hash probes make the compact summary useful; and the possibility of collisions is exactly why “maybe” must never be treated as “present.”