AlgoScope

Bloom Filter

structureintermediateTime O(k) per operationSpace O(m) bits, about 10 per key for 1% false positives

A hash set answers membership exactly and stores every key to do it. A Bloom filter answers approximately and stores nothing but bits: insert a key by setting the bits that k hash functions name, query by reading the same bits. One bit still 0 is proof the key was never inserted, so a "no" is always right. All bits 1 means "probably", because other keys may have set them, and that false positive is the price of the memory saved. Nothing can be removed and the members cannot be listed, which is fine for the job it does: a cheap first question in front of an expensive lookup.

00010203040506070809010011012013014015

A Bloom filter of 16 bits and 3 hash functions, all bits 0. Insert cat, dog, owl, cow, then ask about cat, ant, bee, eel. Each word maps to 3 bit positions; inserting sets them, querying reads them. The filter never stores the words themselves.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.

  1. "cat" hashes to 6, 4, 0. What can the filter say?

    • Definitely not in the set
    • Probably in the set
    • Definitely in the set

    Answer: Probably in the set. A single 0 bit is proof of absence. All 1 bits are only evidence: another word may have set them, so the filter can never say definitely yes.

  2. "ant" hashes to 7, 3, 3. What can the filter say?

    • Definitely not in the set
    • Probably in the set
    • Definitely in the set

    Answer: Definitely not in the set. A single 0 bit is proof of absence. All 1 bits are only evidence: another word may have set them, so the filter can never say definitely yes.

  3. "bee" hashes to 2, 0, 4. What can the filter say?

    • Definitely not in the set
    • Probably in the set
    • Definitely in the set

    Answer: Probably in the set. A single 0 bit is proof of absence. All 1 bits are only evidence: another word may have set them, so the filter can never say definitely yes.

  4. "eel" hashes to 12, 2, 14. What can the filter say?

    • Definitely not in the set
    • Probably in the set
    • Definitely in the set

    Answer: Definitely not in the set. A single 0 bit is proof of absence. All 1 bits are only evidence: another word may have set them, so the filter can never say definitely yes.

How it runs, step by step

  1. A Bloom filter of 16 bits and 3 hash functions, all bits 0. Insert cat, dog, owl, cow, then ask about cat, ant, bee, eel. Each word maps to 3 bit positions; inserting sets them, querying reads them. The filter never stores the words themselves.

    Bloom filter with 16 bits and 3 hashes.

  2. Insert "cat": its three hashes are 6, 4, 0, so those bits become 1. 3 of 16 bits are now set.

    Insert cat: bits 6, 4, 0.

  3. Insert "dog": its three hashes are 12, 6, 2, so those bits become 1, 1 of them already set by an earlier word. 5 of 16 bits are now set.

    Insert dog: bits 12, 6, 2.

  4. Insert "owl": its three hashes are 4, 6, 10, so those bits become 1, 2 of them already set by an earlier word. 6 of 16 bits are now set.

    Insert owl: bits 4, 6, 10.

  5. Insert "cow": its three hashes are 11, 13, 1, so those bits become 1. 9 of 16 bits are now set.

    Insert cow: bits 11, 13, 1.

  6. Query "cat": hashes 6, 4, 0. All three bits are 1, so the answer is "probably", and here it happens to be right: "cat" was inserted.

    cat: probably present.

  7. Query "ant": hashes 7, 3, 3. Bit 7 is 0, and inserting "ant" would have set it, so the word was never inserted. Definitely not.

    ant: definitely absent.

  8. Query "bee": hashes 2, 0, 4. All three bits are 1, so the filter says "probably", but "bee" was never inserted: its bits were set by other words. A false positive, the price of using 16 bits instead of storing the words.

    bee: probably present.

  9. Query "eel": hashes 12, 2, 14. Bit 14 is 0, and inserting "eel" would have set it, so the word was never inserted. Definitely not.

    eel: definitely absent.

  10. 4 words set 9 of 16 bits. Of 4 queries, 2 came back "probably", 1 of them wrongly, and the rest "definitely not", which is never wrong. The false positive rate falls with more bits per key and rises as the filter fills; with about 10 bits per key and 7 hashes it is around 1 percent, at a fraction of the memory a hash set of the keys would need.

    9 bits set; 1 false positives.

Remember

  • Insert sets k bits; query reads them. A single 0 bit proves absence.
  • All k bits set means probably present: other keys may have set them, so false positives happen, false negatives never.
  • No deletes and no listing; about 10 bits per key and 7 hashes give a 1 percent false positive rate.

Topics covered

Related

Where this is used

DatabasesLSM-tree storage engines

RocksDB, LevelDB and Cassandra spread data across dozens of immutable SSTable files, and the same key can sit in several of them at once, so a point read walks the candidate files newest first until it finds one. Each file carries a small Bloom filter kept in memory: a "no" skips that file with no disk I/O at all, and only the files that answer "probably" are actually read. This is why a lookup for a key that does not exist, the common case in a write-heavy store, costs a few bit tests instead of a dozen disk seeks.

SecuritySafe Browsing in the browser

Chrome cannot ask Google about every URL you open, for latency and privacy reasons, and cannot ship the full blocklist either. Early Chrome kept a Bloom filter over hashed prefixes of blocklisted URLs, so nearly every page cleared locally with no network call and only a "probably" escalated to a server check for the full hash. The one-sided error is what made that safe: a blocklisted URL can never come back as a clean "no". Chrome swapped the filter for a sorted prefix set in 2012, which is more compact for a list that is rebuilt rather than inserted into, but the design it established is still the standard shape for a filter sitting in front of a remote lookup.

NetworkingDeciding what a CDN bothers to cache

A large share of the objects a CDN edge server is asked for are requested exactly once, and writing those to disk evicts content that would have been reused. Akamai's servers keep a Bloom filter of URLs seen before and admit an object to the cache only on its second request, at a cost of a few bits per URL rather than storing the URL itself. A false positive just admits a one-hit object early, which is the harmless direction of the error.

Developer toolsDeduplicating an event or ID stream

Remembering every message ID already processed in a set grows without bound, while RedisBloom's BF.ADD and BF.EXISTS hold hundreds of millions of IDs in about ten bits each. The trade to understand is the direction of the error: a false positive here means a genuinely new event is wrongly treated as a duplicate and dropped. That is only acceptable where losing a rare item costs less than processing a duplicate, which is true for view counts and false for payments.

Why it works this way

Why k hash functions instead of just one?

With a single hash the filter is a bit array where any collision is a false positive, so the error rate is roughly the fraction of bits that are 1. With k probes a false positive needs all k of them to land on bits someone else set, which drives the rate down to roughly that fraction raised to the power k. But every insert also sets k bits, so a larger k fills the array faster. The two effects balance at k = (m / n) * ln 2, which is exactly the point where about half the bits are 1; a filter far from half full is mis-tuned.

Why you cannot delete by clearing the bits back to 0

Bits are shared between keys, and the bit you clear may be one of the k bits another key depends on. Clearing it turns that key's query into a false negative, which breaks the one guarantee the structure actually makes. If you need deletes, a counting Bloom filter replaces each bit with a small counter (4 bits is typical) that goes up on insert and down on delete, at four times the memory, and a cuckoo filter stores short fingerprints instead of bits and deletes properly.

You do not need k independent hash functions

Computing k separate hashes of every key would make insert and query k times more expensive than they need to be. Real implementations take one strong 128-bit hash such as MurmurHash3 or xxHash, split it into two halves h1 and h2, and derive probe i as (h1 + i * h2) mod m. Kirsch and Mitzenmacher showed this double-hashing trick gives asymptotically the same false positive rate as k independent functions, and Guava's BloomFilter is built this way.

The size has to be chosen before the first insert

m and k are derived from the number of keys you expect and the error rate you will accept, and there is no resize afterwards: growing the array means rehashing every key, and you never stored the keys. A filter sized for a million entries that receives ten million is close to all-ones and answers "probably" to everything, silently, with no error and no crash. When the count is unknown the usual fixes are a scalable Bloom filter, which chains progressively larger and tighter filters and queries each in turn, or rebuilding the filter from the source data on a schedule.

Read more

Next up