Bloom Filters and Their Role in Safe Browsing
Every time your browser warns you before opening a site — "this page ahead is dangerous" — it just answered a question in a few microseconds: is this URL on a blacklist of millions of known-bad pages? It didn't download that whole blacklist to check. It ran the URL through a Bloom filter, a small bit array that can hold a rough summary of a huge set in a tiny footprint.
• A Bloom filter never says yes for certain — only maybe.
• It never says maybe when the true answer is no — a "not present" result is always trustworthy.
• The trade for that speed and tiny memory footprint is a small, tunable chance of a false positive.
Core Idea: One Bit Array, Several Hash Functions
A Bloom filter is just an array of m bits, all starting at 0, plus k independent hash functions. Adding an item and checking an item use the exact same mechanism:
- Adding an item: run it through all k hash functions, each producing an index between 0 and m−1, and set every one of those bits to 1.
- Checking an item: run it through the same k hash functions. If any of those bits is still 0, the item was definitely never added. If all of them are 1, the item was probably added — but maybe not.
- Why "probably": those bits could have been set by other items entirely. Once a bit is 1, the filter has no memory of which item set it.
- No deletions: a plain Bloom filter can't remove an item, since clearing a bit might belong to several items at once.
Worked Example: A Local Malicious-URL Filter
Say a browser keeps a tiny local Bloom filter — m = 16 bits, k = 3 hash functions — as a first-pass check before it ever has to call out to a full blacklist server. Three known-bad URLs get added: evil.com, trap.net, and badsite.io.
hash = 5381 + seed×33, then for every character c in the string, hash = hash×33 + charCode(c). The final index is hash mod m. Each of the k hash functions uses the same formula with a different seed, so the k lanes behave independently.
Adding the three URLs
Step by Step: How One Index Gets Calculated
The trace above skips straight to the final indices. Here's what actually happens inside a single hash function, worked through by hand for evil.com going into Hash Function 1 (seed = 13). Each hash function processes the string item::s, where s is the hash function's own number — that's what makes lane 1, lane 2, and lane 3 land on different bits even though they're hashing the same item.
- Start with the seed.
hash = 5381 + seed × 33. For seed 13:5381 + 13×33 = 5810. - Build the exact string to hash. Hash Function 1 uses
s = 0, so the string becomes"evil.com::0". - Fold in one character at a time. For every character c, update
hash = (hash × 33) + charCode(c), then keep only the lowest 32 bits (so the number can't grow forever). - Repeat step 3 until the string is exhausted — all 11 characters of
"evil.com::0"get folded in, one after another. - Take the final hash mod m. Whatever 32-bit number is left after the last character gets reduced to a value between 0 and m−1 — that's the array index.
The full character-by-character trace
| step | character | char code | hash after this step |
|---|---|---|---|
| start | — | — | 5810 |
| 1 | e | 101 | 191,831 |
| 2 | v | 118 | 6,330,541 |
| 3 | i | 105 | 208,907,958 |
| 4 | l | 108 | 2,598,995,426 |
| 5 | . | 46 | 4,162,470,480 |
| 6 | c | 99 | 4,217,539,763 |
| 7 | o | 111 | 1,739,858,818 |
| 8 | m | 109 | 1,580,766,255 |
| 9 | : | 58 | 625,678,921 |
| 10 | : | 58 | 3,467,535,267 |
| 11 | 0 | 48 | 2,759,514,163 |
index = 2,759,514,163 mod 16 = 3
That's exactly the first index reported for evil.com above. The other two lanes run the identical process — same five steps — just starting from a different seed and hashing "evil.com::1" and "evil.com::2" instead:
Three lanes, three different seeds, three different indices — [3, 5, 7] — which is exactly what the earlier trace showed. Every add and every check in this whole post is just this five-step process, run k times per item.
Bit array after all three inserts
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| bit | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
Querying: Is This URL Dangerous?
Six URLs come through the browser's address bar. Running each through the same three hash functions:
- →
evil.com→ indices [3, 5, 7] → all set → flagged (correct — it really was added) - →
trap.net→ indices [2, 4, 6] → all set → flagged (correct) - →
badsite.io→ indices [8, 10, 12] → all set → flagged (correct) - →
google.com→ indices [0, 2, 4] → bit 0 is unset → cleared, definitely not on the list - →
safe-bank.com→ indices [11, 13, 15] → bit 11 is unset → cleared, definitely not on the list - →
quiz.biz→ indices [2, 4, 6] → all set → flagged... but this domain was never added
but "quiz.biz" is not in the added set → FALSE POSITIVE
(it happens to hash to the exact same three cells trap.net already stained)
That last case is the entire cost of using a Bloom filter: quiz.biz never touched the filter, but it landed on the same three cells that trap.net already lit up, so the filter can't tell them apart. This is exactly why browsers don't trust a Bloom filter hit as the final word — a "maybe" from the local filter triggers a real lookup against the full blacklist, while a "definitely not" is trusted immediately and skips that network call entirely. That's the actual saving: most URLs a person visits are clean, so most checks end at the local filter and never need a server round trip.
Why It's Efficient
- → A blacklist of tens of millions of URLs, stored as raw strings, could run into gigabytes. A Bloom filter summarizing the same set typically needs only a few bits per entry.
- → Both adding and checking an item take O(k) time — a handful of hash computations — regardless of how many items are already in the filter.
- → The false-positive rate is tunable: bigger m or more careful choice of k pushes it down, at the cost of more memory.
For n items stored in an m-bit array with k hash functions, the expected false-positive probability works out to approximately:
Summary Table
| Aspect | Detail |
|---|---|
| Purpose | Test whether an item is (probably) in a set, using far less memory than storing the set |
| Storage | m bits, independent of how large the actual items are |
| Structure | Bit array + k independent hash functions |
| Add | Set k bits per item |
| Query | Check k bits — any 0 means definitely absent, all 1s means possibly present |
| False negatives | Never happen |
| False positives | Possible, at a rate that grows with how full the filter is |
| Deletions | Not supported in the basic version |
Python Implementation
The same hashing scheme used above, written out as a small class. Running it reproduces the exact bit array and the exact false positive from the walkthrough.
class BloomFilter:
"""A Bloom filter using a djb2-style hash, seeded per hash function."""
def __init__(self, m: int, k: int):
self.m = m
self.k = k
self.bits = [0] * m
self.added_items = []
@staticmethod
def _default_seed(i: int) -> int:
return i * 97 + 13
def _djb2(self, s: str, seed: int) -> int:
h = 5381 + seed * 33
for ch in s:
h = ((h << 5) + h) + ord(ch)
h &= 0xffffffff
return abs(h)
def _indices(self, item: str):
return [
self._djb2(f"{item}::{s}", self._default_seed(s)) % self.m
for s in range(self.k)
]
def add(self, item: str) -> None:
for idx in self._indices(item):
self.bits[idx] = 1
self.added_items.append(item)
def check(self, item: str) -> str:
indices = self._indices(item)
if not all(self.bits[i] == 1 for i in indices):
return "definitely not present"
if item in self.added_items:
return "possibly present (true positive)"
return "possibly present (false positive)"
if __name__ == "__main__":
bf = BloomFilter(m=16, k=3)
for url in ["evil.com", "trap.net", "badsite.io"]:
bf.add(url)
print("bit array:", bf.bits)
for url in ["evil.com", "trap.net", "badsite.io", "google.com", "safe-bank.com", "quiz.biz"]:
print(f"check('{url}') -> {bf.check(url)}")
check('evil.com') -> possibly present (true positive)
check('trap.net') -> possibly present (true positive)
check('badsite.io') -> possibly present (true positive)
check('google.com') -> definitely not present
check('safe-bank.com') -> definitely not present
check('quiz.biz') -> possibly present (false positive)
Advantages
- → Tiny memory footprint compared to storing the actual set.
- → Constant-time adds and checks, regardless of how many items are stored.
- → Zero false negatives — a "not present" answer can always be trusted outright.
Disadvantages
- → Can't confirm membership with certainty — a "maybe" always needs a fallback check when it matters.
- → Items can't be removed without a variant like a counting Bloom filter.
- → Choosing m and k badly lets the false-positive rate climb fast as the filter fills up.