Bloom Filters: Skipping Lookups That Can Only Miss

A Bloom filter is a fixed-size data structure that records which items have been added to a set and answers one question about any item: definitely not in the set, or possibly in the set. A Bloom filter never reports "not in the set" for an item that was added, but a small percentage of queries about items that were never added come back as "possibly in the set" anyway. Those wrong answers are called false positives, and the rate at which they happen is a number you choose when you size the filter.

What you get in exchange for that inaccuracy is memory. A Bloom filter stores no keys, only bits, so a filter holding a million items occupies the same space whether those items are 8-byte integers or 2-kilobyte URLs. At a 1% false positive rate that space is about 1.14 MB, which we will measure against the 88 MB a JavaScript Set used for the same million keys.

In the full article

• The Cost of a Lookup That Finds Nothing
• How a Bloom Filter Works
• A Bloom Filter in TypeScript
• Sizing: Bits per Item and the False Positive Rate
• What a Bloom Filter Cannot Do
• Where They Are Used
• When to Skip the Bloom Filter
• Key Takeaways