# Bloom Filters

A probabilistic set membership structure that can say definitely-not-present or probably-present, using very little space.

**Rests on:** Modular Arithmetic

*Machine Learning · Data Structures*


## Why learn this

Before you can appreciate how a modern AI system answers a question in milliseconds, you need to see how it ruthlessly avoids doing unnecessary work. Bloom filters are the workhorse of that laziness. They sit in front of expensive lookups in databases, in the caching layers of web services, and inside the retrieval machinery of retrieval-augmented generation (RAG). When you later study **Hash Functions** — which you have notes on — you will see exactly why a Bloom filter uses several of them. And when you move on to **B-Trees** and the database indexes behind them, you will recognize the same idea: spend a little space to save a lot of time. This concept unlocks your ability to read systems papers and source code where Bloom filters appear as an unexplained optimization — after this page, they will be a familiar friend rather than a mystery.


## The intuition

Imagine you are a librarian in a vast library. A visitor asks, 'Is the book _The Idiot_ by Dostoevsky on the shelf?' You don't want to walk the entire library every time. Instead, you have a small notebook of clues. For each book you shelve, you write a few distinctive marks in the notebook — say, a checkmark next to certain page numbers. To answer, you quickly flip to those page numbers and see if all the checks are there. If any check is missing, you are certain the book is not present. If all checks are there, the book *might* be present — but you are not fully sure, because another book could have left the same marks. You then do the slow, exact lookup only when the notebook says 'maybe'. That notebook is a Bloom filter. It is a compact way to ask 'is this item possibly in the set?' with two guarantees: if it says 'no', it is definitely not there; if it says 'yes', it might be there — but the chance of a wrong 'yes' is something you control by the size of the notebook and the number of marks you make.


## An analogy

Picture a busy security guard at a concert gate. The guard has a clipboard with a long list of names — the VIP list. The list is huge, and checking each name takes time. To speed things up, the guard has a small card with a grid of boxes, some marked with an X. For each VIP, when they were added, the guard marked a few specific boxes (say, boxes 3, 17, and 42) with an X. When someone claims to be a VIP, the guard checks those three boxes. If any box is empty, the person is definitely not on the list — they are turned away without a full search. If all three boxes are marked, the guard says 'you might be on the list, let me check the full list to be sure.' The card is tiny and fast to check. But here is the catch: if two different names happen to mark the same boxes, a non-VIP could pass the preliminary check and get the guard to waste time on a full lookup — but that waste is rare and cheap. The guard's card is the Bloom filter, and the full list is the exact store. The card works beautifully because it only ever says 'no' with certainty or 'maybe' with a controllable probability. Where the analogy stops working: the guard's card is static (VIPs are added once), whereas a Bloom filter can have items added over time, but you cannot remove an item without rebuilding the whole filter. Also, the guard's card has a fixed number of boxes; in a real Bloom filter you choose the size based on how many items you expect and how many false positives you can tolerate.


## Definition

A Bloom filter is a space-efficient probabilistic data structure that tests set membership: it can report 'definitely not present' with 100% certainty, or 'probably present' with a chosen false positive rate, using a bit array and several independent hash functions.


## How it connects

You have notes on **Hash Functions**, which map any key to a fixed-size index — a Bloom filter uses several of these to generate the positions to set. The idea of trading space for speed connects to your notes on **Balanced Trees and B-Trees**, where tree structures sacrifice memory to keep operations logarithmic. Bloom filters are the extreme of that trade: they use far less space than any exact structure, but give up the ability to say 'yes' with certainty. They also relate to **Heaps and Priority Queues** in that both are specialized structures — you use a heap when you want the min/max, and a Bloom filter when you want a quick membership check that can tolerate errors. Unlike a hash table, which stores the actual items, a Bloom filter stores only a fingerprint, so it cannot list the items or handle deletions.


## The mathematics

The mathematics behind a Bloom filter is simple arithmetic — counting and multiplying — not calculus or algebra. You need no more than addition and multiplication to understand it. A Bloom filter is an array of bits (each bit is either 0 or 1), initially all 0. When you add an item, you pass it through several hash functions. Each hash function produces a number, and you treat that number as a position in the array. You set every one of those positions to 1. To check if an item is in the set, you run the same hash functions on the query item and look at all the resulting positions. If any of them is 0, the item is definitely not in the set (because if it had been added, those positions would have been set to 1). If all of them are 1, the item *might* be in the set — but it could also be a false positive, because different items can cause the same positions to be set. The false positive rate depends on two things: the size of the array (more bits mean fewer collisions) and the number of hash functions (more hashes mean more chances to collide, but also make it harder for a random item to accidentally match all of them). You can calculate the probability mathematically, but the intuition is that with a well-chosen size and hash count, the false positive rate can be made as small as you like — at the cost of more space or more computation. The key mathematical fact is that you never get false negatives — if the filter says 'no', it is always correct.

For a filter with m bits and k hash functions, after inserting n items, the probability that a particular bit is 0 is (1 - 1/m)^(kn), so the false positive rate is approximately (1 - e^(-kn/m))^k. The optimal number of hash functions is k = (m/n) * ln(2). Each symbol: m = number of bits in the array, k = number of hash functions, n = number of items inserted, e = Euler's number (about 2.718), ln = natural logarithm.


## A worked example

```
Let's build a tiny Bloom filter by hand. We have a bit array of size 10 (positions 0 to 9), initially all 0s: [0,0,0,0,0,0,0,0,0,0]. We will use two hash functions. For simplicity, imagine our hash functions give us: h1('cat') = 3, h2('cat') = 7; h1('dog') = 3, h2('dog') = 8. (In reality, hash functions are complex, but for this example we'll treat them as fixed numbers.) We want to add 'cat' and 'dog' and then check 'bird'.

Step 1: Add 'cat': set positions 3 and 7 to 1 → array becomes [0,0,0,1,0,0,0,1,0,0]   # We take the two hash outputs for 'cat' and set those bits to 1.
Step 2: Add 'dog': set positions 3 and 8 to 1 → array becomes [0,0,0,1,0,0,0,1,1,0]   # Position 3 was already 1 (from 'cat'), so it stays 1; position 8 becomes 1.
Step 3: Check 'bird': h1('bird') = 2, h2('bird') = 7. Look at positions 2 and 7. Position 2 is 0, so answer: 'bird' is NOT in the set.   # If 'bird' had been added, both bits would be 1. Since one is 0, it's impossible.
Step 4: Check 'cat': h1=3, h2=7. Both are 1, so answer 'maybe present' — correct in this case.   # A positive result triggers a full lookup if needed.

Result: The filter correctly said 'bird' is not present (definitely, because a bit was 0) and 'cat' is probably present (both bits were 1). Now imagine 'fox' with h1('fox')=3, h2('fox')=8 — both bits are 1 (set by 'dog' and 'cat'), so the filter would say 'maybe present', but 'fox' was never added. That's a false positive, and the rate of such events is what you control.
```


## From scratch, in Python

```python
class BloomFilter:
    def __init__(self, size, num_hashes):
        self.size = size
        self.num_hashes = num_hashes
        self.bits = [0] * size

    def _hashes(self, item):
        # Simple hash function using Python's built-in hash, but we need
        # k different hashes. We'll use a deterministic combination.
        result = []
        for i in range(self.num_hashes):
            # Use a different seed for each hash
            h = hash(item + str(i)) % self.size
            result.append(h)
        return result

    def add(self, item):
        for h in self._hashes(item):
            self.bits[h] = 1

    def contains(self, item):
        for h in self._hashes(item):
            if self.bits[h] == 0:
                return False
        return True

# Example usage
bf = BloomFilter(10, 2)
bf.add("cat")
bf.add("dog")
print(bf.contains("cat"))  # True (probably)
print(bf.contains("bird"))  # False (definitely)
bf2 = BloomFilter(100, 5)
bf2.add("apple")
print(bf2.contains("apple"))  # True
print(bf2.contains("banana")) # False
```


## The same thing, with a framework

In practice, you would not use NumPy or PyTorch for a Bloom filter — it is a simple data structure with no matrix math. But you might use a library like `pybloom_live` or `bloom_filter`. For example:

```python
from pybloom_live import BloomFilter
bf = BloomFilter(capacity=1000, error_rate=0.001)
bf.add('cat')
bf.add('dog')
print('cat' in bf)  # True
print('bird' in bf) # False
```

Under the hood, that library does exactly what our plain Python does: it allocates a bit array (often a Python `bytearray` for efficiency), applies several cryptographic hashes, and sets/checks the bits. The `error_rate` parameter is used to compute the optimal `size` and `num_hashes` automatically.


## What the code does

The `__init__` method sets up the filter: `size` is how many bits we have (we'll use a list of 0s and 1s), and `num_hashes` is how many hash functions we'll use. The `_hashes` method generates k different positions by taking the built-in `hash()` of the item plus a string of the index, then taking modulo `size` to stay in range. `add` iterates over those positions and sets each bit to 1. `contains` checks each position: if any is 0, we return False; if all are 1, we return True. This is exactly the mathematics we did by hand. Notice that `size` and `num_hashes` are chosen by you — they determine the false positive rate. In practice, you'd use a proper hashing library like `hashlib` to avoid Python's `hash()` randomization.


## Common misconceptions

**Bloom filters can be used for exact membership** — A Bloom filter can tell me if an item is in the set for sure.

It can only say 'definitely not' or 'probably yes'. A positive result might be a false positive due to hash collisions. In fact: A Bloom filter is probabilistic: 'no' is certain, 'yes' is 'maybe'. Use it as a pre-filter and confirm with an exact store when it says 'yes'.

**You can remove items from a Bloom filter** — I can just set a bit back to 0 when I delete an item.

That bit might be shared by several items. Clearing it would cause false negatives for those other items, which violates the core guarantee. In fact: You cannot delete from a standard Bloom filter. If you need deletion, use a counting Bloom filter (where each position stores a count) or rebuild the filter.

**More hash functions are always better** — Adding more hash functions makes the filter more accurate.

More hashes set more bits, which increases the chance of collisions. There is an optimal number, given by the formula k = (m/n)ln(2). Too many hashes actually increase the false positive rate. In fact: The number of hash functions must be chosen carefully. Too few and you get more false positives; too many also increases false positives. The optimum is around 0.7 * (number of bits per item).

**Bloom filters store the actual items** — After adding an item, I can retrieve it from the filter.

The filter only stores a pattern of bits, not the item itself. It cannot list or retrieve items. In fact: A Bloom filter answers 'is this item possibly in the set?' It does not store data. Think of it as a sticky note that says 'maybe', not a filing cabinet.


## In short

A Bloom filter is a bit array and several hash functions that answer 'is this item possibly in the set?' with zero false negatives and a controllable false positive rate. It uses little space, is fast, and is ideal as a pre-filter before an expensive exact lookup. Remember: 'no' is definite, 'yes' is a maybe — and you cannot delete items without rebuilding.


## Where this is used

Bloom filters appear all over AI systems, though they are seldom named in the headlines. Here are the places you will actually meet them.

**Large language models (LLMs) — vocabulary filtering and cache lookups.** When a language model generates text, it has to check each token against a vocabulary list. If a token is not in the model's vocabulary, it is ignored. Instead of a giant hash table, some implementations use a Bloom filter as a pre-filter: if the filter says 'definitely not', the model skips it. Another place is in the attention mechanism, where you sometimes need to check if a given key appears in a set of keys — a Bloom filter can speed up that check. In practice, a developer might write: `if not vocab_filter.contains(token): continue` to avoid a slow string comparison.

**Small language models on devices (TinyML).** On a phone or a microcontroller, memory is precious. A Bloom filter with a few thousand bits can replace a dictionary of tens of thousands of words. For example, a wake-word detector might maintain a set of known voice-command hashes. When a new audio frame comes in, it quickly checks if the hash is possibly known before doing the full neural network inference. That saves battery and CPU time.

**Retrieval-augmented generation (RAG).** In RAG, the system first retrieves a handful of relevant documents from a large corpus, then feeds them to an LLM. The retrieval step often uses an approximate nearest-neighbour index, but before that, a Bloom filter can act as a first-stage pre-filter: if a document's ID is not in the filter of relevant document IDs, it is skipped without doing a vector similarity search. This cuts the number of candidates from millions to hundreds. A developer might write: `if not bloom_filter.contains(doc_id): return None` before running the expensive embedding comparison.

**Agentic systems (planning and tool use).** Agents that call tools need to decide whether a tool call is valid. They often maintain a list of allowed function names or URL patterns. A Bloom filter can quickly reject an invalid call. Also, when an agent caches responses from previous calls, a Bloom filter can tell it whether a query has likely been seen before, avoiding a slow cache lookup. The mechanism is the same: filter first, then exact check only on a positive.

**Everyday applied ML — recommendation, fraud detection, web caching.** Recommendation systems often use Bloom filters to avoid recommending items the user has already seen. When a system serves ads or suggestions, it checks a Bloom filter of 'seen' item IDs; if the filter says 'no', it can skip the recommendation. Fraud detection systems use them to store hashes of known fraudulent credit card numbers — a quick check filters out the vast majority before any deeper analysis. Web caches (like Squid or Varnish) use Bloom filters to determine which URLs might be in the cache, saving a disk lookup when the answer is a clear no.

**What a developer actually writes.** In each case, the pattern is the same: create a filter with an expected number of items and a target false positive rate (say 1%), then call `add` on every item you want to remember, and test with `contains` on every incoming query. The cost of a false positive is an extra, unnecessary exact lookup; the benefit is that false negatives are impossible, so you never miss a real hit.

**What breaks when it is done badly.** The two common failures are: (1) choosing too small a filter, which drives the false positive rate up so high that the filter is almost always saying 'maybe', negating its benefit; (2) using a non-uniform hash function, which causes some bits to be set more often than others, again increasing false positives. Also, forgetting that deletions are not allowed — if you need to remove items, a Bloom filter is the wrong tool, and you should use a counting Bloom filter or a different structure.


---

Read this on the web: https://basavapurushottam.com/learn-ai/bloom-filters
