What Is a Bloom Filter? Probabilistic Set Membership

A Bloom filter is a compact, probabilistic data structure that answers one question fast and cheaply: “is this item possibly in the set, or definitely not?” It can never produce a false negative — if it says an item isn’t in the set, that’s guaranteed correct — but it can produce false positives, occasionally claiming an item is present when it isn’t. In exchange for that small, tunable margin of error, a Bloom filter uses dramatically less memory than actually storing every item, which is exactly the trade real systems are usually happy to make.

The core idea

A Bloom filter is built on a fixed-size array of bits, all initialized to 0, plus a handful of independent hash functions. Adding an item runs it through each hash function, and each hash result points to a position in the bit array, which gets set to 1. Checking whether an item might be present runs it through the same hash functions and checks whether every one of those positions is already set to 1.

• If any of those positions is still 0, the item was definitely never added — that’s a guaranteed “no.”
• If all of those positions are 1, the item was probably added — but it’s also possible that combination of bits got set by some other items’ hashes overlapping by coincidence. That’s the source of the false positive.

This is a very different contract than a hash table, which stores actual keys and can answer membership questions with certainty. A Bloom filter throws away the actual items entirely — it only keeps a compact fingerprint of everything that’s been added, which is exactly why it needs so much less memory.

Why false positives (but never false negatives)

The asymmetry is a direct consequence of how the bits work. Setting a bit to 1 is a one-way operation shared across every item — the array has no idea which item set which bit, so a bit is a permanent superposition of every item that ever hashed to it. Once a bit is 1, nothing can make it definitively “belong” to only one item again.

That’s why false positives happen: enough different items’ hash outputs can coincidentally light up all the same bit positions an unrelated item would need, making the filter claim a false match. But false negatives are structurally impossible — an item that was genuinely added always set its own bits to 1, and bits set to 1 are never cleared back to 0 in a standard Bloom filter, so those positions are guaranteed to still be 1 whenever that same item is checked again.

Tuning the error rate

The false-positive rate is controllable, not fixed, and depends on three things: the size of the bit array, the number of hash functions, and how many items have actually been inserted. A larger bit array relative to the number of items lowers the odds of a collision; more hash functions spread each item’s fingerprint across more bits, which helps up to a point but eventually starts making the array fill up faster and hurts more than it helps.

In practice, engineers pick a target false-positive rate (say, 1%) and use standard formulas to size the bit array and hash function count for the expected number of items. The trade-off is fundamental and can’t be escaped, only tuned: a smaller filter means a higher false-positive rate; a lower false-positive rate means more memory.

What you can’t do with a Bloom filter

A few limitations follow directly from the design:

• No deletion. Because a single bit can be shared by many items’ hashes, clearing a bit to remove one item might silently break membership checks for other items that also depend on that bit. (A variant called a Counting Bloom Filter solves this by using small counters instead of single bits, at the cost of more memory.)
• No retrieval of the actual items. A Bloom filter can only answer “is this specific item probably present,” never “what items are in this set.” It stores no actual data, just a fingerprint.
• Accuracy degrades as it fills. A Bloom filter sized for a certain number of items gets progressively less accurate — more false positives — the more items get added beyond that budget.

Where Bloom filters show up

The classic use case is avoiding expensive lookups for items that definitely don’t exist. A database or key-value store like Redis can keep a Bloom filter in memory in front of a much slower on-disk lookup: check the filter first, and if it says “definitely not present,” skip the disk read entirely. Only when the filter says “maybe” does the system pay for the real, authoritative lookup — and because false positives are rare by design, that expensive path is only taken occasionally.

Other common applications include web browsers checking URLs against a large blocklist without downloading the entire list, spell checkers testing whether a word might be in a dictionary, and distributed systems checking for duplicate work across nodes without shipping the full data set between them. In every case, the pattern is the same: a fast, memory-cheap first filter that only needs to be right about the “definitely not present” case, with a slower, authoritative check as the fallback for anything that passes.

Bloom filters vs hash tables

	Hash table	Bloom filter
Memory usage	Stores full keys (or references)	Stores only a compact bit fingerprint
False positives	Never	Possible, at a tunable rate
False negatives	Never	Never
Can retrieve items	Yes	No — membership only
Deletion	Supported	Not supported (without extensions)

The takeaway

A Bloom filter trades certainty for a huge reduction in memory: it can guarantee an item isn’t in a set, but can only say an item is “probably” present, with a tunable false-positive rate. That asymmetry is exactly what makes it useful as a fast pre-check in front of an expensive, authoritative lookup — skip the costly path when the filter says no, and only pay for the real check on the rare occasions it says maybe.