Benefits & Limitations of Bloom Filters

A Bloom filter is a deliberate trade. You give up exact answers and the ability to delete, and you get back memory and speed. This lesson lays out both sides so you can decide when the trade is worth making.

Benefit 1: It Uses Very Little Memory

This is the reason Bloom filters exist. A hash table or a set stores every item you put into it. If the items are one hundred byte URLs, one million of them cost around one hundred megabytes.

A Bloom filter stores no items at all. It stores a bit array whose size you choose up front