Explaining Bloom Filters

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 engineer on the domains team at Vercel.

In the tweet, Dillon mentioned using four different Bloom filters 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. 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 groceries: apples, onions, bread, milk, and more. 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:

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).

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).

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 how are words turned into indexes? You may know the answer to that question already: hashing.

Hashing is a deterministic way of turning a string into a number: the same input always produces the same output

A simple Hash Implementation

Because hashing is deterministic, the same string always gives the same output. Try it above: 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 even a formula for how many hash functions to use:

_{k = (m/n) × ln(2)}

where m is the size of the bit array and n is the number of items you expect to store. In plain English: the roomier the array is relative to the data, the more hash functions are worth running.

This is the trick used by Bloom filters.

Adding Everything Together

Now try it yourself: type a word and press the arrow. Three different hash functions run on the same word, produce three positions, and those three bits flip from 0 to 1. The filter already holds apples, eggs, and onions — that’s why some bits start out as 1 — and whatever you add joins them.

Adding items to a Bloom filter

Notice that the array itself never grows. Adding an item only flips bits in place. Add a few more words and watch the ones accumulate.

The payoff: checking for membership

Checking works exactly like adding, just without flipping anything. Run the word through the same three hash functions and look at those three bits. If any of them is 0, the word was definitely never added. If all three are 1, the filter says “maybe”.

The filter below is the same one you just filled: it started with apples, eggs, and onions, plus whatever you added above. Check for one of them, then check something that was never added. And when you’re done, check asleep.

Checking membership and catching a false positive

Did you catch it? asleep was never added, but it happens to hash to the exact same three positions as onions. All three of its bits are already 1, and the filter says “maybe”. That is a collision, and it is why a Bloom filter can only ever say maybe: it can guarantee when something is not in the set, but it can only probably confirm when something is. Better hash functions and a bigger bit array don’t eliminate collisions; they just make them rarer.

Back to that tweet

Remember Dillon’s four layered Bloom filters? Now the trick makes sense. When someone searches for a domain on Vercel Domains , the question “is this domain definitely not taken?” can be answered instantly. No database lookup, just a handful of bit checks. Only the “maybe” cases have to take the expensive path. That’s the whole magic: a fixed array of bits, a few hash functions, and honest answers of “definitely not” or “maybe”.