Bloom Filter: Probabilistic Set Membership

A bit array standing in for a set

Burton Howard Bloom described this structure in 1970 as a way to test set membership without storing the set itself. A Bloom filter is an array of m bits, all initially 0, plus k independent hash functions. To insert an item, hash it k times and set the k bits those hashes point to. To query whether an item might be in the set, hash it the same k times and check whether all k of those bits are set - if even one is 0, the item was definitely never inserted; if all k are 1, the item is probably in the set.

live demo · bits lighting up as items hash into the array● LIVE

No false negatives, tunable false positives

This is the entire value proposition in one sentence: a Bloom filter never reports that an inserted item is absent, but it can, with some probability, report that an item is present when it never was inserted. The false positive happens when unrelated insertions happen to have already set all k of a new query's bit positions, purely by hash collision. There is no mechanism for a false negative, because insertion only ever sets bits and never clears them.

function add(item) {
  for (let i = 0; i < k; i++) bits[hash(item, i) % m] = 1;
}
function mightContain(item) {
  for (let i = 0; i < k; i++)
    if (bits[hash(item, i) % m] === 0) return false;   // definitely not in the set
  return true;                                          // probably in the set
}

The false-positive formula

After inserting n items into an m-bit array with k hash functions, the probability that any single bit is still 0 is approximately e to the power of minus kn over m. The probability that a query for a never-inserted item finds all k of its bits set by coincidence is therefore approximately (1 minus e to the power of minus kn over m) raised to the power k. This expression is minimised, for fixed m and n, when k equals (m over n) times the natural log of 2 - roughly 0.693 bits worth of hash functions per bit of budget per item. Plugging that optimum back in gives the well-known rule of thumb that about 10 bits per item and 7 hash functions yields roughly a 1 percent false-positive rate.

Why it is worth the false positives

A hash set that stores the items themselves would need memory proportional to the number and size of the items. A Bloom filter needs only a fixed-size bit array, independent of how large or complex the items are, at the price of an occasional wrong "maybe". This trade-off is ideal as a pre-filter in front of something expensive: a database checking whether a key might exist before a costly disk read, a web crawler skipping URLs it has probably already visited, a CDN or router deciding whether a cache probably has an item before making a network round trip, or a spell-checker testing whether a word is probably valid before a full dictionary lookup.

Variants worth knowing

A counting Bloom filter replaces each bit with a small counter, incremented on insert and decremented on delete, which restores support for removal at the cost of several times the memory. A cuckoo filter stores short fingerprints in a cuckoo hash table instead of raw bits, supports deletion natively, and at low false-positive rates uses less memory than a Bloom filter for the same guarantee - the modern default when deletion matters.

Frequently asked questions

Can a Bloom filter ever miss an item that was actually inserted?

No, never - that is the one guarantee it never breaks. Inserting an item always sets its k bits, and once a bit is set it is never cleared in a standard Bloom filter, so every bit that a query checks for a previously inserted item is guaranteed to already be set. False positives are possible; false negatives are structurally impossible.

Can you remove an item from a Bloom filter?

Not from the standard version, because clearing a bit might belong to several items due to hash collisions and would silently reintroduce false negatives for the others. A counting Bloom filter, which stores a small counter instead of a single bit per slot, supports deletion by decrementing instead of clearing, at the cost of more memory.

Why not just use a hash set instead?

A hash set stores the actual items, so its memory grows with the size and count of the items themselves. A Bloom filter stores only a fixed-size bit array regardless of item size, typically 10 bits per item for a 1 percent false-positive rate, which is why it is used as a fast, memory-cheap pre-filter in front of a slower, exact lookup such as a disk read.

Try it live

Everything above runs in your browser - open Bloom Filter and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Bloom Filter simulation