How a Bloom Filter Works: Build One From Scratch in Python

布隆过滤器的工作原理：从零开始用 Python 实现

2026年6月29日

/

#Python

Prasanth Madhurapantula

布隆过滤器给你一种近乎魔法的体验：它仅用几千字节的内存，就能判断某个项目是否存在于数十亿项目的集合中。无论存储的数据量有多大，它的响应时间始终保持在极短的范围内。

这听起来似乎不可能。普通的集合必须记住每个项目，因此其内存消耗会随着数据量增长。但布隆过滤器几乎不记得项目本身的任何信息，却仍然能回答成员资格问题。关键在于，它允许在特定可控的方向上出现错误。

这并非魔法，当你自己构建一个布隆过滤器时，这个技巧就会变得清晰，你也会完全理解它能承诺什么和不能承诺什么。

在本教程中，我们将仅使用一个比特列表和几个哈希函数，从零开始在 Python 中构建一个可用的布隆过滤器。到教程结束时，你将理解位数组、为何使用多个哈希函数、什么是假阳性、布隆过滤器永不违背的唯一保证，以及如何根据目标错误率调整布隆过滤器的大小。

目录

• 布隆过滤器的本质
• 简要历史
• 布隆过滤器的应用场景
• 核心思想：位数组与几个哈希函数
• 将项目转换为位置
• 添加与检查
• 假阳性是常态
• 根据目标错误率调整大小
• 布隆过滤器的局限：无法删除
• 综合实现

布隆过滤器的本质

布隆过滤器是一种概率数据结构。它的全部作用就是回答一个问题："这个项目在集合中吗？"，它仅给出两个可能的答案：

• 肯定不在集合中。这个答案始终正确。
• 可能存在于集合中。这个答案通常正确，但偶尔会出错。

令人惊讶的是，它在不存储任何项目的情况下就能回答问题。普通的集合（如 Python 的 set 或哈希表）会保存所有见过的项目，因此其内存消耗会随着项目数量和每个项目的大小而增长。

布隆过滤器只保存一个固定长度的比特行。其大小在初始化时确定，此后永不改变，无论你存储的是短单词、长 URL 还是完整文件。

因此，布隆过滤器本质上不是一个容器，更像是集合的指纹。你无法要求它列出内部内容或返回某个项目，你只能询问："你是否可能见过这个？"，你可以完全信任它的"否"回答。

一个快速的想象方式：与其保存一个宾客名单，你保存的是一堵灯开关墙。当宾客到达时，你根据他们的名字选择几个开关进行切换。要检查某人是否来过，你查看他们的开关状态。如果任何一个开关是关闭的，他们肯定没来过。如果所有开关都打开，他们很可能来过，尽管可能有其他人的名字触发了这些开关。

这个比喻也解释了为何你会选择布隆过滤器而非普通集合。对于一百万个平均每个50字节的 URL，真实集合需要几十兆字节内存，且随着 URL 长度增长而增加。而同样一百万个项目的布隆过滤器，在1%错误率下仅需约1.2兆字节固定内存，无论 URL 多长。

当集合非常庞大、需要在每台机器的内存中存储、或包含大型项目时，这种内存节省的差异可能让某些方案从"不可行"变为"可行"。代价是罕见的假阳性，但通常的使用模式让这种代价变得低廉：一个"否"回答可以跳过昂贵的查找操作，而"是"回答只会触发你本就需要执行的较慢精确检查。

经验法则：如果你需要精确答案、删除操作，或者能够列出存储内容的能力，请使用真正的集合。如果你需要一个体积小、速度快的门禁系统，它位于昂贵操作之前，并能可靠地告诉你何时可以跳过该操作，请使用布隆过滤器。

简要历史

这种数据结构以 Burton Howard Bloom 命名，他在 1970 年发表于《ACM 通讯》的论文 "允许错误的哈希编码中的时空权衡" 中首次描述了这一结构。

他的原始动机示例非常普通。一个需要对文本进行连字符处理和拼写检查的程序，需要在字典中查找单词，但将整个字典存储在 1970 年代有限的内存中成本过高。Bloom 的想法是接受少量可控的错误，以换取巨大的空间节省。这种单次权衡——允许少量错误以节省大量内存——正是为什么这种结构在 50 多年后仍然广泛应用于许多大型系统的原因。

布隆过滤器的应用场景

你今天很可能已经使用过基于布隆过滤器的软件。它们在以下领域非常重要：

• 数据库和存储引擎：Cassandra、HBase、Bigtable 以及许多基于日志结构（LSM-tree）的存储系统，为每个磁盘文件都维护一个布隆过滤器。在执行缓慢的磁盘读取前，引擎会询问过滤器："这个键可能存在于该文件中吗？" 如果得到否定回答，就可以完全跳过该文件，从而避免大量读取操作。

• 安全浏览：早期版本的 Google Chrome 会将每个 URL 与本地存储的已知危险网站布隆过滤器进行比对。否定回答意味着安全，无需网络请求；肯定回答非常罕见，会触发对完整列表的真正检查。

• 缓存和 CDN：一个常见技巧是仅在某个项目被请求至少两次后才进行缓存。布隆过滤器可以廉价地记住"我是否之前见过这个项目？"，从而过滤掉大量一次性请求。

• 推荐系统：Medium 曾描述使用布隆过滤器来避免推荐用户已经阅读过的文章。

• 网络和加密：路由器使用布隆过滤器来识别重复数据包，早期的比特币轻客户端使用它来请求相关交易，而无需暴露具体关心的地址。

结构始终如一。布隆过滤器总是位于某些昂贵操作（磁盘读取、网络请求、数据库查询）之前，将大部分昂贵检查转换为几次快速的数组读取。现在让我们构建一个布隆过滤器，看看具体实现方式。

核心思想：位数组和几个哈希函数

布隆过滤器基于两个组件构建：

• 位数组：一个由 0 开始的长位序列。

• 若干哈希函数：每个哈希函数将一个项目转换为数组中的某个位置。

添加一个项目时，你会将其通过每个哈希函数处理，得到多个位置，并将这些位置对应的位设置为 1。

检查一个项目时，你会通过相同的哈希函数处理它，并查看相同的位置。如果所有位置都是 1，该项目"可能存在"；如果至少有一个位置是 0，该项目"肯定不存在"。

第二个结果非常重要。如果某个位仍然是 0，你可以确定从未添加过任何会导致该位被设置为 1 的项目。过滤器永远不会遗漏它实际见过的项目。

以下是 Python 中的完整结构实现：

import hashlib

class BloomFilter:
    def __init__(self, size, num_hashes):
        self.size = size              # 数组中的位数（m）
        self.num_hashes = num_hashes  # 哈希函数数量（k）
        self.bits = [0] * size        # 每个位初始为 0

将项目转换为位置

我们需要为每个项目生成 num_hashes 个不同的位置，并且这些位置需要均匀分布。一个常见且简洁的技巧是使用双哈希：计算两次独立的哈希值，然后将它们组合起来生成所需数量的位置。

def _positions(self, item):
    data = item.encode("utf-8")
    h1 = int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
    h2 = int.from_bytes(hashlib.md5(data).digest()[:8], "big")
    for i in range(self.num_hashes):
        yield (h1 + i * h2) % self.size

这里同时发生了三件事：

• 使用 sha256 和 md5 生成的 h1 和 h2 是两个大数值，对于相同字符串具有稳定性，且在不同字符串间看起来随机。

• h1 + i * h2 通过将它们与不同的 i 值组合，使每个位置的值都不同，从而实现位置的分散分布。

• % self.size 将每个值折叠到 0 到 size-1 的有效索引范围内。

对一个项目运行此函数，可以得到 num_hashes 个位置。这些位置就是该项目在过滤器中的指纹。

添加和检查

添加操作会将每个位置对应的位设置为 1。检查操作会确认这些位是否全部被设置。

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

def __contains__(self, item):
    return all(self.bits[idx] for idx in self._positions(item))

定义 __contains__ 方法让我们可以使用 Python 自然的 in 语法。我们来尝试一下：

bf = BloomFilter(size=1000, num_hashes=4)
bf.add("alice")
bf.add("bob")

print("alice" in bf)   # True
print("bob" in bf)     # True
print("carol" in bf)   # 几乎总是 False

"carol" 从未被添加过，因此它的四个位中至少有一个几乎肯定仍然是 0，过滤器会报告其不存在。这是常见情况。但请注意 "almost certainly" 这个限定词，这正是下一节要讲述的全部内容。

误报是常态

位是共享的。当添加足够多的项目后，恰好编码为 "carol" 的四个位可能已经被其他项目设置为 1，即使 "carol" 本身从未被添加过。当发生这种情况时，过滤器会错误地报告 "carol" 可能存在。这就是误报。

刚接触布隆过滤器的人有时会认为这是个错误。其实不是。这是使用极小内存所付出的代价，而且是可以调整的。你可以通过将大量项目塞入小型过滤器来观察这一现象：

bf = BloomFilter(size=200, num_hashes=4)
for i in range(100):
    bf.add(f"user-{i}")

# 以下项目从未被添加过，但有些会错误地显示为存在：
false_hits = sum(f"ghost-{i}" in bf for i in range(1000))
print(false_hits)  # 非零数值：误报率的体现

不过，过滤器在另一个方向上永远不会出错。你添加的每个 user-i 仍然会返回 True，因为添加项目会设置所有对应的位，而这些位永远不会被清除。这是布隆过滤器始终保证的：

• "不存在" 的判断永远正确。永远不会出现误漏。

• "存在" 的判断可能错误。误报是可能发生的。

这种不对称性正是布隆过滤器的实用之处。浏览器可以维护一个已知恶意网址的布隆过滤器，并能立即检查每个链接。"不存在" 意味着链接是安全的，无需进一步处理。"存在" 的情况较为罕见，只会触发对真实列表的较慢精确检查。过滤器将大多数查询转换为几次数组读取操作。

为特定错误率调整大小

误判率取决于三个数值：位数组大小 m、预期添加的项目数 n，以及哈希函数数量 k。近似误判率公式如下：

p = (1 - e^(-k*n/m)) ** k

你无需猜测这些参数。给定项目数 n 和目标误判率 p，可以直接计算出最优的 m 和 k：

import math

def optimal_params(n, p):
    m = math.ceil(-n * math.log(p) / (math.log(2) ** 2))  # 所需位数
    k = max(1, round((m / n) * math.log(2)))               # 建议使用的哈希函数数量
    return m, k

print(optimal_params(1_000_000, 0.01))  # 约 (9_585_059, 7)

仔细阅读这个结果。若要以 1% 的误判率追踪一百万个项目，需要约 960 万个比特（约 1.2 兆字节）和 7 个哈希函数。

实际处理一百万个字符串的成本会高得多，且大部分成本随字符串长度增加而增长。Bloom 过滤器不关心项目长度，只关心项目数量。

无法实现的功能：删除操作

还有一个诚实的限制需要说明。你不能通过清除位来删除项目，因为这些位是共享的。清除 "alice" 的位可能会同时清除 "bob" 依赖的位，导致 "bob" 错误地报告不存在，从而破坏“无误漏”的承诺。

如果需要删除功能，标准解决方案是使用计数 Bloom 过滤器，其中每个槽位是一个小计数器而非单个比特。添加操作会增加计数器，删除操作会减少计数器，当计数器值大于零时槽位视为“已设置”。这种方式需要更多内存，这是典型的权衡。

综合说明

我们构建的组件及其成本如下：

操作 | 成本 --- | --- add | O(k) in (检查) | 空间 约 | m 比特 用于 | n 个项目，与项目大小无关

关键要点：

• Bloom 过滤器由位数组和几个哈希函数组成。添加操作设置 k 个比特，检查操作询问这些 k 个比特是否全部被设置。
• “否”总是正确的。“是”可能是误判，误判率可通过调整 m 和 k 来优化。
• 它体积小且速度快，因为它存储的是指纹而非实际项目，因此会忘记项目原本的具体内容。
• 没有计数变体的情况下无法实现删除，因为比特是共享的。

下次系统告诉你“这个项目肯定不在缓存中，无需查找”或“这个项目可能是已知项目，让我再确认一下”时，你将清楚背后的技术原理：一组比特、几个哈希函数，以及一个被允许出错的方向。

如果你喜欢通过构建而非记忆来学习数据结构，这就是我创建的 IWTLP 平台的核心理念，其中这个 Bloom 过滤器是数据工程课程中的一个动手实践练习。

我不是职业软件工程师，也不是为了创建编程网站而学习编码。我是航空推进领域的研究生，也是网络安全从业者，我自学编程是为了在热爱的各个领域（从燃气轮机循环分析到恶意软件取证）进行跨领域构建。这一切成为可能的原因是，我在某个时刻停止了语法记忆，开始真正理解计算，这成为我最实用且最有趣的工具。

如果这篇文章对你有帮助，请分享它。

免费学习编程。freeCodeCamp 的开源课程已帮助超过 40,000 人成为开发人员。立即开始

ADVERTISEMENT