Explaining Bloom Filters - A Guide

Oct 14, 2025 - 4 min read

Introduction

I’ve been meaning to write this post for a while—welcome to my corner of the internet! A while back, I came across a tweet by Dillon, a former engineeer on the domains team at vercel.

screenshot of Dilion's tweet

In the tweet, Dillon mentioned using four different Bloom filter in a layered cache to make domain search faster on Vercel Domains. That got me curious—what’s a Bloom filter, and why use it this way?

So I decided to build one from scratch. After some tinkering (and a few “aha!” moments), it finally worked! I showed it to a few CS friends, and now I’d love to share what I learned with you.

Hey friends 👋, let’s dive in!

What is a bloom filter?

A Bloom filter is a probabilistic data structure used to quickly check whether an item might be in a set. Notice that word—might. Let’s make that concrete with a simple analogy.

Imagine you’re shopping with your mum. You pack a bag with apples, eggs, onions, and vegetables. Later, she asks:

Do we have eggs in the bag?

One way to check is to go through everything in the bag one by one. That’s what a traditional search does, it scans the whole list until it finds a match (or not). On a computer, this is what that would look like:

1x
Speed
Searching for:
apples
#0
apples
#1
eggs
#2
vegetable
#3

How traditional search would work

But what if your bag could hold millions of items? Searching one by one would take forever! That’s where a Bloom filter comes in, it lets you quickly check if something might be there, without searching the entire list.

The tradeoff? You might get false positives (it says something is there when it’s not), but you’ll never get false negatives (it will never say something isn’t there when it actually is).

Probabilistic Search: Is legldntlegndltnegd

What’s the trick up a Bloom filter’s sleeve?

Surprisingly, Bloom filters do not actually store data directly. Instead, the filter uses a bit array (an array of zeros and ones).

0
0
0
0
0
0
0
0
0
0

An Empty Bloom Filter

So, how are items added to the filter? This is the interesting part specific indexes are flipped from 0 to 1 meaning that part is filled. So, Howare words turned into indexes. You may know the answer to that question already, hashing.

Hashing is a one-way function for turning strings for into random numbers

1572909631

A simple Hash Implementation

Because hashing is a one-way function it would always give the same output for the same string. victor always returns 226095160. A Bloom filter uses several hash functions to map an item to different positions in the bit array and flips those bits from 0 to 1. There is actually a formula to find out how many hash functions to use.

This is the trick used by bloom filters.

Adding Everything Together

5

75

55

0
0
0
1
0
2
0
3
0
4
1
5
0
6
0
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
16
0
17
0
18
0
19
0
20
0
21
0
22
0
23
0
24
0
25
0
26
0
27
0
28
0
29
0
30
0
31
0
32
0
33
0
34
0
35
0
36
0
37
0
38
0
39
0
40
0
41
0
42
0
43
0
44
0
45
0
46
0
47
0
48
0
49
0
50
0
51
0
52
0
53
0
54
1
55
0
56
0
57
0
58
0
59
0
60
0
61
0
62
0
63
0
64
0
65
0
66
0
67
0
68
0
69
0
70
0
71
0
72
0
73
0
74
1
75
0
76
0
77
0
78
0
79
0
80
0
81
0
82
0
83
0
84
0
85
0
86
0
87
0
88
0
89
0
90
0
91
0
92
0
93
0
94
0
95
0
96
0
97
0
98
0
99

Later, if you check for “eggs”, the same hash function(s) are used. If the corresponding bits are all 1, then the filter says “eggs” was probably added before.

Why “probably”? Because different items can sometimes hash to the same index — this is called a collision. For example, hashing “Victor” and “Kalu” might return the same result, making the Bloom filter think both items exist when only one was added.

Even if you use better hash functions, collisions can still occur. That’s why Bloom filters give you probabilistic answers — they can guarantee when something is not in the set, but they can only probably confirm when something is in the set.