How Bloom Filters Work: Hash Bits, False Positives, and Why Deletion Is Hard

A cache, a database, and a CDN edge often need the same cheap answer: have I seen this key before? Storing every key is correct and expensive. A Bloom filter stores a compact bit array instead. After you insert a key, a later membership query never says “absent” if the key was inserted. It may say “present” for a key that was never inserted. That one-sided error is the entire contract.

This article is about that contract: how several hash functions paint bits, why false positives are inevitable and tunable, why a classic filter cannot delete, and where the structure shows up in real systems. It is not a second explanation of consistent hashing, B-tree indexes, or cache eviction. Those decide where a key lives or which page to keep. A Bloom filter only answers a probabilistic set-membership question.

The contract

Fix a bit array of length m, initially all zeros, and k independent hash functions that map a key to k positions in 0 .. m-1.

• Insert(x) sets those k bits to 1.
• MightContain(x) returns true only if all k bits are already 1. If any bit is 0, x was never inserted.

False negatives are forbidden by construction. False positives happen when some other combination of inserts happens to set the same k bits. There is no list of keys inside the structure, so you cannot enumerate members and you cannot prove presence. You can only prove absence.

Why a hash set is the wrong tool for this job

A hash table that stores the keys themselves uses memory proportional to the number of keys times the key size, plus load-factor slack. That is the right structure when you must retrieve the key or attach a value. It is wasteful when the only question is “should I even look on disk?”

LSM-tree storage engines face that question on every point lookup. A level may contain millions of keys. Reading a table file to discover that the key is not there is a wasted I/O. A Bloom filter of a few bytes per key, kept in memory or in a file header, lets the engine skip the file. A false positive costs one extra read. A false negative would hide a real row, which is unacceptable, so the filter is built so that path cannot happen.

How the bits actually get set

Take a tiny filter: m = 16 bits, k = 3 hash functions. Insert "apple". Suppose the three hashes land on positions 2, 7, and 11. Those three bits become 1. Insert "mango" at 4, 7, and 14. Bit 7 was already 1; the others flip. The array now has ones at 2, 4, 7, 11, and 14.

Query "apple": bits 2, 7, 11 are all 1, so the filter says maybe. Query "kiwi" with hashes 2, 8, and 11: bit 8 is still 0, so the answer is definitely not present. Query "pear" with hashes 4, 7, and 14: all three bits are 1 even though "pear" was never inserted. That is a false positive. Nothing in the array records which key painted bit 7.

In production code you rarely maintain k unrelated hash functions. A common construction is double hashing: compute two 64-bit hashes h1 and h2, then use (h1 + i * h2) mod m for i = 0 .. k-1. The independence is not perfect. For filter sizes used in databases and caches it is close enough that the textbook false-positive formula still predicts observed rates.

The false-positive formula, used as a sizing tool

After inserting n distinct keys into m bits with k hashes, a standard approximation for the false-positive probability is

(1 - e^{-kn/m})^k

Two design moves follow from that expression.

First, for a target n and a tolerated false-positive rate p, the number of bits you need is about

m ≈ -n ln(p) / (ln 2)^2

which is roughly 10 bits per key for p ≈ 1% and about 7 bits per key for p ≈ 2%. That is why people quote “a byte or so per key” as a working budget, not as a law.

Second, the k that minimizes p for a given m/n is about

k ≈ (m/n) ln 2

which is 7 hashes at 10 bits per key. More hashes are not automatically better. Each extra hash sets more bits, which fills the array faster and eventually raises the collision rate.

These are approximations that assume ideal hashes and that n is known when you allocate m. If you undersize the array and keep inserting, p climbs toward 1 and the filter becomes a very expensive way to always say yes. Growing a classic Bloom filter in place is not free: you must allocate a larger array and re-insert every original key, which you no longer have unless you kept them elsewhere. That is why many systems size the filter from a known key count (an SSTable that is already sealed) rather than from a live, unbounded stream.

Why deletion is hard

Clearing the k bits of a key you want to remove also clears bits that other keys still depend on. After deleting "mango" in the 16-bit example by turning off 4, 7, and 14, a later query for "apple" sees bit 7 at 0 and reports absent. That is a false negative, which violates the contract.

Counting Bloom filters replace each bit with a small counter. Insert increments; delete decrements; a query treats a zero counter as a zero bit. Saturating a counter, or choosing a counter width so narrow that overflow is common, reintroduces errors. The memory cost is no longer one bit per slot. For many cache and LSM use cases that cost is not worth it, so they rebuild filters when files are compacted instead of deleting individual keys.

A blocked Bloom filter changes layout, not the deletion story. It hashes a key to a cache-line-sized block and then sets bits only inside that block so probes stay in one cache line. False-positive math changes slightly. You still cannot turn bits off safely.

A compact implementation sketch

The following Python is a teaching model, not a library. It uses two 64-bit hashes derived from SHA-256 only so the example has no extra dependency on a specialized hash. A real filter would use a faster non-cryptographic hash.

import hashlib

class BloomFilter:
    def __init__(self, m, k):
        self.m = m
        self.k = k
        self.bits = 0  # treat as an m-bit integer

    def _indexes(self, key):
        raw = hashlib.sha256(key.encode()).digest()
        h1 = int.from_bytes(raw[:8], "little")
        h2 = int.from_bytes(raw[8:16], "little") or 1
        return [ (h1 + i * h2) % self.m for i in range(self.k) ]

    def add(self, key):
        for i in self._indexes(key):
            self.bits |= (1 << i)

    def might_contain(self, key):
        return all(self.bits & (1 << i) for i in self._indexes(key))

Exercise the contract with a few strings and you will see definite negatives and occasional false positives as n grows relative to m. You will not see a false negative unless you mutate bits by hand.

Where this shows up

Cassandra, RocksDB, and LevelDB attach Bloom filters to SSTables so point reads can skip files. Postgres can use Bloom indexes for columns that appear together in AND predicates but are individually unselective. Chrome has used a Bloom filter of Safe Browsing hostnames so the browser can avoid a network check for the vast majority of URLs. Akamai and other CDNs have used filters to decide whether a mid-tier might hold an object before requesting it. Bitcoin nodes use Bloom filters in an older lightweight-client protocol to request a subset of transactions; that design has well-known privacy limits and is not a recommendation, but it is a clear membership-filter use.

In every case the economics are the same. Memory for bits is cheap compared with I/O or a round trip. A small false-positive rate is cheaper than storing the full set at that layer.

Related structures that are not the same idea

A hash set answers membership exactly and stores keys. A cuckoo filter stores fingerprints in buckets and can delete a fingerprint, at the cost of a more complicated insert that may kick existing fingerprints around. A quotient filter packs fingerprints into a compact array with run metadata. HyperLogLog estimates cardinality, not membership. Count-Min sketch estimates frequencies. Reusing the phrase “probabilistic data structure” does not make those interchangeable with a Bloom filter.

Consistent hashing, covered separately on this site, maps a key to a node. A Bloom filter does not place data. Putting both in the same sentence because they both use hash functions hides the different questions they answer.

Misconceptions

A Bloom filter can say a key is present. It can say a key is absent, or that it might be present. Treat a positive as “go check the source of truth.”

More hash functions always reduce errors. Past the optimum k, extra hashes fill bits faster and raise p.

You can delete by clearing bits. Not in the classic structure, unless you accept false negatives.

The filter replaces the database. It is a guard in front of a slower exact structure. The exact structure still exists.

Cryptographic hashes are required. They are not. You need well-distributed bits. Speed usually wins over cryptographic strength here.

Takeaways

A Bloom filter is a bit array plus k hash functions. Insert sets bits. A query that finds a zero bit is a definite miss. A query that finds only ones is a maybe, with a false-positive rate you choose when you pick m, n, and k. The structure never lists its keys, so it cannot delete them safely and cannot be resized without the original key set. Used in front of disk, a network hop, or a larger index, that is often the right trade: a few bits per key and a rare extra lookup, instead of storing every key at the fast layer.

Related reading on this site: How Consistent Hashing Works, Database Indexing Explained, and How Caching Works.