How Does a Bloom Filter Work?

A Bloom filter is a compact probabilistic data structure used to answer a membership question:

Could this item be in a set?

It is designed to make this decision using a small array of bits and several hash functions. Instead of storing the original items, a Bloom filter stores a compact pattern produced from those items. That pattern can quickly identify items that are definitely absent. However, it cannot always prove that an item is present.

This leads to the most important rule for understanding a Bloom filter:

• If the filter says no, the item is definitely not present.
• If the filter says yes, the item might be present.

The second result may be a false positive: the filter can say that an item might be present even when that item was never inserted. False positives are a normal and fundamental part of the design, not an implementation error.

This article explains the complete process with a small example: a 12-bit array and three hash functions. The array is intentionally tiny so that every change can be displayed clearly. The same reasoning applies when the array is larger.

The basic components​

A basic Bloom filter has two main components:

1. A bit array containing zeros and ones.
2. Several hash functions that map an item to positions in that array.

A bit array with 12 positions initially looks like this:

Index:  0 1 2 3 4 5 6 7 8 9 10 11
Bits:   0 0 0 0 0 0 0 0 0 0  0  0

Each position contains either 0 or 1. A zero means that the position has not been marked. A one means that the position has been marked by at least one insertion.

The positions are numbered from 0 through 11. When a hash function produces a value, that value must be converted into one of those valid positions. For this explanation, assume that the filter uses three hash functions:

h1(item)
h2(item)
h3(item)

Each function receives the same item and produces one array position. For example, the three functions might map an item named A to positions 2, 5, and 9:

h1(A) = 2
h2(A) = 5
h3(A) = 9

The filter does not store the string A in its array. It simply sets bits 2, 5, and 9 to one.

Why use several hash functions?​

A single hash function would map an item to only one position. A different item might happen to map to the same position, making it easy for unrelated items to look similar. Using three hash functions gives each item three positions instead of one.

For an item x, we can describe those positions as:

p1 = h1(x)
p2 = h2(x)
p3 = h3(x)

The item is represented by the combination (p1, p2, p3). During insertion, all three positions are marked. During a query, all three positions are checked.

This does not eliminate collisions. Two different items can still share one position, two positions, or all three positions. It does, however, require a possible match to satisfy several bit checks rather than just one.

The hash functions are therefore central to the process. Insertion and querying must use the same functions and the same mapping from items to positions. If an item is inserted using one set of positions but queried using a different mapping, the query would not be checking the information that insertion recorded.

A complete 12-bit example​

Let us begin with the empty filter:

Index:    0 1 2 3 4 5 6 7 8 9 10 11
Initial:  0 0 0 0 0 0 0 0 0 0  0  0

Suppose the three hash functions produce the following positions for several items:

These values are illustrative hash results. They make the bit operations visible without requiring a particular hash-function implementation.

Several observations will matter later:

• A maps to positions 2, 5, and 9.
• B maps to positions 1, 5, and 10.
• C maps to positions 0, 4, and 8.
• D maps to the same three positions as A in this example.
• X maps to positions 3, 6, and 11.

The fact that A and D have the same positions demonstrates that the bit pattern does not preserve item identity. The filter only sees positions and bit values; it does not know which original item led to a particular one.

Inserting the first item​

Insertion means applying all three hash functions and setting the resulting positions to one.

Start with the empty array:

Index:    0 1 2 3 4 5 6 7 8 9 10 11
Bits:     0 0 0 0 0 0 0 0 0 0  0  0

Insert A. Its positions are:

h1(A) = 2
h2(A) = 5
h3(A) = 9

Set positions 2, 5, and 9 to one:

Index:    0 1 2 3 4 5 6 7 8 9 10 11
After A:  0 0 1 0 0 1 0 0 0 1  0  0

The filter now contains three marked positions. It does not contain a retrievable copy of A. The only information stored is that positions 2, 5, and 9 are one.

At this point, those three bits are evidence that could be consistent with A having been inserted. They are not labeled as belonging to A, and the filter does not know whether another item might later use one or more of the same positions.

Inserting a second item​

Now insert B. Its hash results are:

h1(B) = 1
h2(B) = 5
h3(B) = 10

Positions 1, 5, and 10 must be set to one. Position 5 is already one because it was set when A was inserted. That is not a problem. Assigning one to a position that already contains one leaves it unchanged.

The resulting array is:

Index:    0 1 2 3 4 5 6 7 8 9 10 11
After B:  0 1 1 0 0 1 0 0 0 1  1  0

The array does not record that position 5 was shared by A and B. It simply remains one. There is no counter in this basic representation and no list showing which items contributed to each position.

This is the accumulating behavior of a basic Bloom filter. Insertion changes zero bits to one, but setting an already marked position does not add a visible distinction to the array.

Inserting a third item​

Insert C, whose positions are 0, 4, and 8:

h1(C) = 0
h2(C) = 4
h3(C) = 8

Set those positions to one:

Index:    0 1 2 3 4 5 6 7 8 9 10 11
After C:  1 1 1 0 1 1 0 0 1 1  1  0

The final state after inserting A, B, and C is therefore:

Index:  0 1 2 3 4 5 6 7 8 9 10 11
Bits:   1 1 1 0 1 1 0 0 1 1  1  0

Positions 3, 6, 7, and 11 are still zero. Positions 0, 1, 2, 4, 5, 8, 9, and 10 are one.

The filter has compressed the three inserted items into this bit pattern. It cannot reconstruct the original collection from the pattern. Its purpose is narrower: it can test whether a queried item's required positions are compatible with the pattern.

The insertion algorithm​

The insertion procedure can be written as simple pseudocode:

function insert(item):
    positions = [h1(item), h2(item), h3(item)]

    for position in positions:
        bits[position] = 1

For every item, the algorithm performs three hash calculations and sets three positions. If two hash functions happen to produce the same position, that position is simply set to one more than once.

The important operation is setting, not toggling. A position must become one and remain one as items accumulate. Toggling would be incorrect because setting the same position again could change it back to zero, which would destroy information about previous insertions.

The insertion operation also does not compare the new item against previously inserted items. It does not search for an existing entry. It only calculates positions and marks bits.

Querying an item that was inserted​

Querying uses the same three hash functions. To query A, calculate its positions again:

h1(A) = 2
h2(A) = 5
h3(A) = 9

Inspect the final bit array:

Index:  0 1 2 3 4 5 6 7 8 9 10 11
Bits:   1 1 1 0 1 1 0 0 1 1  1  0

The relevant positions are:

bits[2] = 1
bits[5] = 1
bits[9] = 1

All three positions are one, so the filter returns a positive-style answer:

A might be present

Since A really was inserted, the answer is correct in this case. Nevertheless, the wording “might be present” is important. The bit array itself does not prove that A caused those bits to become one.

A query checks the positions; it does not repeat the insertion or recover the original item. The filter can only evaluate the current state of the bits.

Querying an item with a zero bit​

Now query X. Its hash results are:

h1(X) = 3
h2(X) = 6
h3(X) = 11

Check those positions in the final array:

bits[3]  = 0
bits[6]  = 0
bits[11] = 0

At least one required position is zero. In fact, all three are zero in this example. The filter can therefore return:

X is definitely absent

Why is this conclusion safe? If X had been inserted, the insertion process would have set positions 3, 6, and 11 to one. Under the normal accumulating behavior of the basic filter, those positions would not later become zero. Finding even one required zero means that X could not have produced the current state through insertion.

A query can stop as soon as it finds the first zero. There is no need to check the remaining positions because one missing required bit is already enough to reject the item.

The central query rule​

For an item x, the query rule is:

if bits[h1(x)] == 0:
    definitely absent
else if bits[h2(x)] == 0:
    definitely absent
else if bits[h3(x)] == 0:
    definitely absent
else:
    possibly present

In compact logical form:

possibly present =
    bits[h1(x)] == 1
    and bits[h2(x)] == 1
    and bits[h3(x)] == 1

The word and is essential. Every position selected by the hash functions must be one before the filter reports a possible match.

If the query finds a zero, the result is definitive. If it finds three ones, the result is only compatible with membership. The same bit may have been set by a completely different item.

How a false positive occurs​

A false positive happens when an item was not inserted, but all of its hash-selected positions have been marked by other insertions.

Use the filter state after inserting A, B, and C:

Index:  0 1 2 3 4 5 6 7 8 9 10 11
Bits:   1 1 1 0 1 1 0 0 1 1  1  0

Suppose D was never inserted, but its three hash functions produce:

h1(D) = 2
h2(D) = 5
h3(D) = 9

All of those positions contain one:

bits[2] = 1
bits[5] = 1
bits[9] = 1

The filter therefore reports:

D might be present

But D was not inserted. This is a false positive.

The filter cannot distinguish this situation from the case where D really was inserted. It sees only three marked positions. Those positions may have been set directly by D, or they may have been set by other items, or they may be shared by several items.

This example is especially direct because D maps to exactly the same positions as A. After A is inserted, the filter has the same visible bit evidence for both values. The filter does not store enough information to tell them apart.

Why false positives are unavoidable in this design​

The filter stores a shared bit array rather than complete item identities. When a bit changes from zero to one, the filter does not attach a name to that change. It records only the fact that the position is marked.

Imagine a board with 12 squares. Each item selects three squares, and insertion marks those squares. Later, a query selects three squares and asks whether they are all marked.

If one selected square is blank, the answer is safely negative. The queried item would have marked that square if it had been inserted.

If all three selected squares are marked, there are two possibilities:

1. The queried item marked them when it was inserted.
2. Other items marked them earlier.

The board cannot tell which possibility occurred because it does not record who marked each square. That loss of identity is the reason a Bloom filter can have false positives.

The design deliberately accepts this uncertainty in exchange for a compact representation and a simple membership test. The important asymmetry is that the false-positive risk affects positive-style results, not negative results, provided the filter is used according to its normal accumulating rules.

Following the array over time​

It is useful to review the complete sequence in one place.

Empty filter​

Index:  0 1 2 3 4 5 6 7 8 9 10 11
Bits:   0 0 0 0 0 0 0 0 0 0  0  0

Insert A at positions 2, 5, and 9​

Bits:   0 0 1 0 0 1 0 0 0 1  0  0

Insert B at positions 1, 5, and 10​

Position 5 was already one, so only positions 1 and 10 visibly change:

Bits:   0 1 1 0 0 1 0 0 0 1  1  0

Insert C at positions 0, 4, and 8​

Bits:   1 1 1 0 1 1 0 0 1 1  1  0

Query A​

Positions 2, 5, and 9 are all one:

possibly present

Query X​

Positions 3, 6, and 11 contain zeros:

definitely absent

Query D​

Positions 2, 5, and 9 are all one, even though D was not inserted:

possibly present  // false positive

This sequence captures the entire mechanism: insertions accumulate marks, queries inspect the marks, and overlapping positions can make an absent item look possible.

What the filter stores—and what it does not store​

A Bloom filter stores a bit pattern. In the example, it stores 12 binary values:

1 1 1 0 1 1 0 0 1 1 1 0

It does not store:

• The original text of each item.
• A list of items associated with each bit.
• A record of how many items set a particular bit.
• A way to identify which item caused a bit to become one.

This distinction explains why the filter is compact but lossy. Once several items have been inserted, the bit array contains combined information. It can be used for the specific question supported by the structure, but it cannot serve as a direct replacement for the original collection when the original values are needed.

For example, after inserting A, B, and C, the final bit pattern does not allow a program to read the array and reconstruct those three names. It can hash a candidate item and compare the candidate's positions with the pattern, but it cannot enumerate the original items from the bits alone.

Why the array size matters​

The example uses only 12 bits. That makes the state easy to display, but it also means the array can become crowded quickly.

After inserting A, B, and C, eight of the twelve positions are one:

1 1 1 0 1 1 0 0 1 1 1 0

If more items are inserted, additional zeros will tend to become ones. As the array becomes more full, it becomes easier for an unrelated item to find all three of its required positions already marked.

In the extreme case, every position is one:

1 1 1 1 1 1 1 1 1 1 1 1

When that happens, every possible query finds ones at its three positions. The filter returns “possibly present” for every item, including items that were never inserted. The filter has not violated its rule—the positive result is still only a possibility—but it no longer rejects absent items effectively.

This illustrates why the array size must be considered together with the expected number of insertions. The 12-bit example is useful for learning the algorithm, but a real configuration needs enough positions for its intended workload.

The number of hash functions matters too​

Each inserted item in this example sets three positions, and each query checks three positions. Changing the number of hash functions changes both operations.

With fewer functions, an item is represented by fewer positions. A query then has fewer conditions that must all be true before it returns a possible match. With more functions, an item is represented and checked at more positions.

The number of functions is therefore part of the filter's behavior, not a cosmetic setting. It determines how many bit accesses are performed for each item and how many conditions an unrelated item must satisfy to produce a positive-style result.

Regardless of the chosen number, the rule remains unchanged:

• Insertion sets every position selected for the item.
• Querying requires every selected position to be one.
• A single zero is sufficient for a definite negative.
• All ones indicate only possible membership.

The three-function version is simply the concrete configuration used throughout this explanation.

Complexity intuition​

For the 12-bit, three-hash-function example, inserting one item requires three hash calculations and up to three bit assignments. Querying one item requires up to three hash calculations and up to three bit checks. A query may finish earlier if it encounters a zero.

The work is tied to the configured number of hash functions rather than to the number of items already inserted. The algorithm does not scan every previously inserted item. It calculates positions for the candidate and examines those positions directly.

The storage shown in the example is exactly 12 bits. The filter stores one binary value per array position, not a complete copy of every inserted item. A larger array uses more bits but follows the same procedure.

The exact cost in a particular implementation depends on the cost of computing the hash functions and accessing the bit array. At the algorithmic level, however, the operations are simple: hash an item, map the results to positions, set or check a small number of bits.

A programmer's pseudocode view​

The insertion and query operations can be expressed as follows:

function insert(item):
    positions = [h1(item), h2(item), h3(item)]

    for position in positions:
        bits[position] = 1

The query operation is:

function mightContain(item):
    positions = [h1(item), h2(item), h3(item)]

    for position in positions:
        if bits[position] == 0:
            return false

    return true

The return value in this pseudocode should be interpreted carefully:

• false means definitely absent.
• true means possibly present.

A name such as mightContain communicates this distinction better than a name that suggests exact membership. The operation does not prove presence when it returns true; it only confirms that none of the required bits contradict the possibility of presence.

A practical two-stage interpretation​

When an exact answer is required, the Bloom filter's positive result should be treated as a reason to perform a more authoritative check, not as final proof.

The logical process is:

1. Hash the candidate item.
2. Check its three positions in the filter.
3. If any position is zero, reject the candidate as definitely absent.
4. If all positions are one, treat the candidate as a possible match.
5. Use the exact source of membership information to decide whether it is really present.

This approach separates fast rejection from exact confirmation. A false positive may lead to an unnecessary follow-up check, but the filter's positive result should not by itself be used as proof that the item exists.

The distinction is especially important when a program performs an action based on membership. The filter can safely support a “definitely not present” conclusion. It cannot safely replace the final membership decision when false positives would matter.

Common mistakes to avoid​

Mistake 1: Reading a positive result as proof​

“All required bits are one” does not mean “the item was inserted.” It means only that the current bit pattern is compatible with insertion. Other items may have set the same positions.

The safe interpretation is:

negative result => definitely absent
positive result => possibly present

Mistake 2: Thinking the filter stores complete items​

The filter stores zeros and ones, not the original values. It cannot recover an inserted item by reading the bit array.

Mistake 3: Assuming a bit belongs to one item​

A single position can be selected by many items. Once it is one, the filter does not record which item or items selected it.

Mistake 4: Forgetting that all three positions are required​

A query is positive-style only when all three positions are one. Finding one zero is enough for a definite negative.

Mistake 5: Using inconsistent hash calculations​

The positions calculated during querying must correspond to the positions calculated during insertion. The same item must map consistently to the same three positions.

Mistake 6: Expecting the tiny example to handle unlimited insertions​

A 12-bit array can demonstrate the algorithm, but it has only 12 positions. As more positions become one, more absent items can pass the all-ones test.

Mistake 7: Treating collisions as exceptional failures​

Overlapping positions are expected. Collisions are part of why the structure is probabilistic. The filter is built around shared bits and the possibility that different items produce the same visible pattern.

A useful mental model​

Think of the filter as a shared board with 12 squares. Every item chooses three squares using the hash functions. Inserting an item marks its three squares.

To query an item, mark mentally the three squares that it would have chosen:

• If one of those squares is blank, the item is definitely absent.
• If all three are marked, the item might be present.

The board remembers which squares are marked, but not who marked them. This single detail explains the entire behavior of the Bloom filter:

• Shared squares make storage compact.
• Shared squares allow different items to overlap.
• Overlap can create false positives.
• A blank required square can still prove absence because insertion would have marked it.

This model is often easier to remember than the implementation details. The algorithm is a shared marking process followed by a shared-position test.

The complete algorithm in one view​

For this three-function, 12-bit configuration, insertion is:

insert(item):
    p1 = h1(item)
    p2 = h2(item)
    p3 = h3(item)

    bit[p1] = 1
    bit[p2] = 1
    bit[p3] = 1

Querying is:

query(item):
    p1 = h1(item)
    p2 = h2(item)
    p3 = h3(item)

    if bit[p1] == 0:
        return definitely absent
    if bit[p2] == 0:
        return definitely absent
    if bit[p3] == 0:
        return definitely absent

    return possibly present

The algorithm is short, but its result semantics are subtle. The filter is not asking, “Can I find the item stored here?” It is asking, “Do any of the bits required for this item contradict the possibility that it was inserted?”

A zero supplies a contradiction. Three ones do not supply proof; they merely remove that contradiction.

Final takeaways​

A Bloom filter uses a bit array and multiple hash functions to create a compact summary of inserted items. In the example, the array has 12 positions and each item is mapped to three positions.

The complete behavior can be summarized as follows:

1. Start with every bit set to zero.
2. Hash an item with all three hash functions.
3. Set the three resulting positions to one.
4. To query an item, calculate the same three positions.
5. If any required position is zero, the item is definitely absent.
6. If all required positions are one, the item might be present.
7. A false positive occurs when an item was not inserted but other items have already set all of its positions.
8. The filter stores a combined bit pattern, not the original items or the ownership of each bit.
9. As more positions become one, absent items are more likely to pass the all-ones test.
10. A positive-style result should be treated as possible membership when exact certainty is needed.

The key sentence to remember is:

Hash an item to several positions, set those positions during insertion, and require all of them to be set during a query—while accepting that an all-set result can be a false positive.

That is how a Bloom filter provides a compact, fast, and intentionally one-sided membership test.