Bloom Filters Explained: Probabilistic Lookups With Massive Memory Savings

A Bloom filter is a probabilistic data structure that uses a bit array and multiple hash functions to determine whether an element is definitely absent from a set or possibly present. It trades a small, configurable rate of false positives for dramatically lower memory usage — storing 1 billion URLs requires roughly 1.25 GB at a 1% error rate, compared to 50–100 GB for full string storage. Insertions and lookups both run in microseconds without hitting a database, making the structure ideal as a fast pre-filter before expensive queries. Deletions are not natively supported, since unsetting a bit could invalidate other elements that share it. Major systems including Google Chrome, Apache Cassandra, Bitcoin SPV wallets, and Akamai CDN rely on Bloom filters to reduce unnecessary disk reads, database queries, and network lookups.