Back to blog

An Interactive Guide to Bloom Filter

6 min read
interactive_blog
bloom filter
data structures

Discover the space-efficient Bloom filter, its workings, hash functions, tuning, and varied applications from database optimization to spam detection

An Interactive Guide to Bloom Filter

Introduction

A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. It saves us from performing expensive queries against our database. While Bloom filters can guarantee that an element is not in the set, they cannot guarantee its presence. Instead, they can sometimes return false positives (indicating an element is in the set when it is not), but they never return false negatives.

Problem

Before diving into how Bloom filters work, let’s consider the problem they solve. Imagine you run a website that needs to process thousands or even millions of requests every second. One of your tasks is to check whether the IP address making a request is in a list of banned IPs.

If you store this list in a traditional database or an in-memory data structure like a hash table, every lookup consumes resources, and lookup time can grow with the size of the list. For every incoming request, querying the database or searching through a large list can severely impact performance.

Wouldn’t it be great if there was a fast, constant-time way to determine whether an IP address is banned without querying the database? Enter Bloom filters.

Prerequisites

Hashing

To understand Bloom filters, you need to be familiar with the concept of hashing. Hashing involves using a hash function to convert input data (like an IP address) into a fixed-size output, often an integer. Good hash functions are deterministic (they always produce the same output for the same input) and uniformly distribute outputs across the available range.

Diagram illustrating a hash function mapping keys to hash values. "1.1.1.1" maps to "00," "2.2.2.2" and "3.3.3.3" map to "05," showing a hash collision. "4.4.4.4" maps to "05." Hash values range from "00" to "06."

How It Works

Bloom filters address the problem of fast membership checks by using multiple hash functions and a bit array. Here’s how it works:

  1. Initialization: A Bloom filter uses a fixed-size bit array of size m, initially set to all zeros. It also uses k independent hash functions.

  2. Adding an element:

    • To add an element, it is passed through all k hash functions.

    • Each hash function maps the element to a position in the bit array, and the corresponding bits at these positions are set to 1.

  3. Checking for membership:

    • To check if an element is in the set, the element is hashed with the same k hash functions.

    • If all the bits at the positions indicated by the hash functions are 1, the filter reports that the element might be in the set.

    • If any of these bits are 0, the element is definitely not in the set.

This design ensures that the Bloom filter is both space-efficient and fast (O(k)O(k) time complexity). However, there is a trade-off: the possibility of false positives, which occurs when bits set by previously inserted elements overlap, making it appear that a new element is in the set when it has never been added.

Here is a tiny Bloom filter guarding the banned-IP list from earlier. Five IPs are already banned. Hover one to see which bits it set, then look up any IP to see the bits it lands on.

Try it · Bloom filter
Bits in the filter (m)32
Hash functions (k)3
Banned IPs · 5
Bit array
13 of 32 set
10
11
12
03
14
05
06
17
08
09
110
011
112
013
014
015
116
017
018
019
020
021
022
123
024
125
026
127
028
129
030
131
Look up an IP
Items (n)
5
Bits set
41%
False positive odds
5.24%
Fooled it
0 / 0
false positives / checks
Hover a banned IP to see the bits it set. Changing m or k rebuilds the filter from the same list.

Things to try:

  • Look up an IP that isn't on the list. Most of the time one of its bits is 0, and the filter knows for sure it was never added.

  • Can you get the filter to return a false positive? Ban a few random IPs and keep checking random ones. When it happens, the filter shows which banned IPs set the bits.

  • Keep banning until every bit is 1. Now every lookup says "probably banned" and the filter is useless.

  • Raise k. Each item now sets more bits, so the array fills up faster.

  • Lower m and watch the false positive odds climb: the same items squeezed into fewer bits collide more often.

Tuning

A real filter holds millions of items, not five, so its size comes down to three numbers:

  • Number of elements n

  • Size of filter m

  • Number of hash functions k

Drag the sliders below to size a filter. Each chart varies one of the three numbers while holding the other two where you set them, and the amber dot marks your filter.

Try it · Tuning a Bloom filter
Items (n)1M
Filter size (m)1.3 MB
Hash functions (k)7
Chance of a false positive
0.819%
10.0 bits per item · 10,000,000 bits total
Best k for this n and m: 6.9
vs. number of items
0%50%100%101K100K10M1B
vs. hash functions (log scale)
100%10%1%0.1%k=1k=10k=20k=30
vs. filter size (bits)
0%50%100%10010K1M100M10B
The amber dot on each chart is your filter. Each chart varies one parameter and holds the other two where the sliders are.

Some conclusions you can draw from the charts:

  • False positive rate vs. number of items follows a logistic curve: a filter does fine until it nears capacity, then saturates quickly.

  • False positive rate vs. number of hash functions follows a U/J-curve: too few hashes and each item is easy to impersonate; too many and the bit array fills up. Use k jumps to the bottom of the U.

  • False positive rate vs. filter size falls steeply as more bits are allocated. Around 10 bits per item with the best k gives roughly a 1% false positive rate, whether you store a thousand items or a billion.

Formulas

1. Probability of a False Positive

The probability of a false positive in a Bloom filter is approximately:

P≈(1−e−knm)kP \approx \left( 1 - e^{- \frac{kn}{m}} \right)^k

Where:

  • m: Number of bits in the Bloom filter.

  • k: Number of hash functions.

  • n: Number of elements inserted into the filter.

2. Optimal Number of Hash Functions

The optimal number of hash functions k to minimize the false positive rate is:

k=mnln⁡2k = \frac{m}{n} \ln 2

3. Expected Fraction of Bits Set to 1

The fraction f of bits in the Bloom filter that are set to 1 after n insertions is:

f=1−(1−1m)knf = 1 - \left( 1 - \frac{1}{m} \right)^{kn}

Alternatives and Variations

  • Cuckoo Filters

    A modern alternative that supports deleting inserted items. It stores fingerprints of inserted items in an array of buckets using cuckoo hashing. It works great for applications needing high lookup throughput, deletions, or large-scale deduplication.

  • Counting Bloom Filters

    Uses a counter array where each position is a small integer instead of a single bit. Lookups, insertions, and deletions are performed by incrementing and decrementing the counters. Works great for applications that require element deletions while maintaining high performance and bounded memory usage.

Applications

Bloom filters have a wide range of real-world applications, including:

  • Database Query Optimization: Reduce disk I/O and lookups by quickly discarding queries for non-existent elements (e.g., in Cassandra, RocksDB, and PostgreSQL).

  • Web Caching: Quickly check if a URL is cached before attempting to fetch it from disk or remote storage.

  • Spam and Malicious URL Detection: Fast pre-checks to determine whether an email sender or URL is present on a blacklist.

  • Distributed Systems: Avoid unnecessary cross-node synchronization and identify duplicate data or requests efficiently.

Further Reading