---
title: 'Bloom Filters: Why They Allow False Positives But Never False Negatives'
source: 'https://youtube.com/watch?v=y1NNF1ZDGSg'
video_id: 'y1NNF1ZDGSg'
date: 2026-08-04
duration_sec: 120
---

# Bloom Filters: Why They Allow False Positives But Never False Negatives

> Source: [Bloom Filters: Why They Allow False Positives But Never False Negatives](https://youtube.com/watch?v=y1NNF1ZDGSg)

## Summary

This video explains Bloom filters, a probabilistic data structure used by Chrome to check URLs against a list of malicious sites without storing the full list. It highlights how Bloom filters trade a small false positive rate for massive memory savings while guaranteeing zero false negatives.

### Key Points

- **The Problem** [00:02] — Chrome needs to check URLs against millions of malicious sites instantly without sending browser history to Google servers. A database lookup on every navigation is too slow and a privacy nightmare.
- **Naive Approach** [00:15] — Downloading the full list of bad URLs and storing them locally in a hash set is impractical because millions of URLs at 50 bytes each would consume too much memory, and the list changes constantly.
- **Bloom Filter Basics** [00:29] — A Bloom filter is a fixed-size bit array. When adding a URL, you hash it into multiple positions and flip those bits. To check membership, you hash again and see if all positions are set.
- **False Positives and Negatives** [01:01] — Bloom filters guarantee zero false negatives (if a URL is on the list, it will be detected), but they can have false positives (a URL not on the list might be flagged) due to bit collisions.
- **Trade-off Acceptable** [01:14] — In Chrome's case, a false positive just means an extra server call to verify a URL that turns out fine, which is acceptable. A false negative (missing a malicious URL) would be a real bug.
- **Memory Savings** [01:27] — Tracking a billion URLs at a 1% false positive rate costs about 1.2 gigabytes, while a hash set storing the same data would be 10 to 20 times more.
- **Other Applications** [01:40] — The same pattern is used in web crawlers to check visited URLs, spam filters, and any system doing high-volume membership testing at scale.

### Conclusion

Bloom filters offer an efficient way to handle membership testing at scale, accepting a small false positive rate in exchange for significant memory savings, making them ideal for applications like Chrome's safe browsing.

## Transcript

you visit against a list of millions of malicious sites instantly without sending your browser history to Google servers? A database lookup on every navigation would be too slow and a privacy nightmare. So, Chrome needs
something that lives on your device. The obvious approach is to download the full list of bad URLs and store them locally in a hash set. It sounds reasonable until you do the math. Millions of URLs at even 50 bytes each blows past what
you want sitting in browser memory. And the list is changing constantly. What you actually need is a way to check membership instantly at scale without storing every URL. Chrome uses a Bloom filter. It's a fixed-size bit array.
When you add a URL to the filter, you hash into multiple positions and flip those bits. To check membership, you hash the URL again and see if all of the positions are set. If any bit is zero, that URL is definitely on the list. If
all of the bits are set, it probably is, but occasionally other entries flip those same bits, giving you what's called a false positive. Bloom filters guarantee zero false negatives, so if it's in the list, you're going to know,
but they trade a configurable false positive rate for massive memory savings. In Chrome's case, a false positive just means you make one extra server call to verify a URL that turns out to be fine. It's acceptable. A false
negative of missing an actually malicious URL would be a real bug. The numbers back it up. Tracking a billion URLs at a 1% false positive rate costs URLs at a 1% false positive rate costs about 1.2 gigs. A hash set storing the
same data would be 10 to 20 times more. The same pattern shows up in web crawlers checking visited URLs, spam filters, and any system doing high-volume membership testing at scale. Want to hear about more tricks like
Want to hear about more tricks like this? Follow us for more system design.