布隆过滤器 转载说明：本文基于 Sam Rose 于 2024-02-19 发布的文章《Bloom Filters》整理与精译。 原文地址：https://samwho.dev/bloom-filters/ 文中的所有交互式图表、可视化组件和按钮演示，均已在 StaticFlow 的“交互原版”中保留。 布隆过滤器是一种非常“偏门”但又极其有用的工具。它并不适合所有问题，但一旦场景匹配，它往往能用极低的空间成本，换来非常可观的性能收益。 它属于概率型数据结构：你用一部分精确性，换取更小的存储占用和更快的判定速度。本文会说明它能做什么、适合什么场景、内部是怎样工作的、该怎么调参，以及为什么“删除”会比“插入”麻烦得多。布隆过滤器能做什么 从接口上看，布隆过滤器很像 Set：你可以往里面添加元素你可以询问某个元素是否存在 但它返回结果的含义，和普通集合并不一样。 对普通 Set 来说：true 就是存在false 就是不存在 对布隆过滤器来说：false 仍然表示“它一定不存在”true 只表示“它也许存在” 这就是它最核心的取舍。当布隆过滤器把一个从未插入过的元素说成“可能存在”时，这种错误叫做假阳性（false positive）。 相反，如果一个数据结构把已经插入的元素说成“不存在”，那叫做假阴性（false negative）。标准布隆过滤器不会产生假阴性，这也是它之所以有价值的根本原因。布隆过滤器什么时候有用 假设你在做一个浏览器，希望在用户访问恶意链接之前给出提醒。 一种最直接的做法是：把所有已知恶意链接维护成一张完整名单，每次用户打开链接时都去查这张表。如果命中，就弹出警告。 这当然可行，但代价也很直接：你需要把整张名单持续分发到每个客户端，而且还要不断更新。 如果我们粗略假设：互联网里有 1,000,000 条恶意链接每条链接平均长度约 20 个字符 那么这份名单大约就是 20 MB。单看这个数字不算夸张，但一旦乘上大量客户端、持续更新和带宽成本，就完全值得优化。 如果你能接受非常低的误报率，那么布隆过滤器可以把空间大幅压缩：若假阳性率控制在 0.0001%，可降到大约 3.59 MB若假阳性率放宽到 0.1%，则只需大约 1.8 MB 这不是纸上谈兵。Google Chrome 在 2012 年之前，就曾经把布隆过滤器用于 Safe Browsing。 而且，如果你不希望最终用户真的看到“误报警告”，还可以采用两段式设计：先在本地检查布隆过滤器如果它返回“肯定不在”，就立即放行如果它返回“也许在”，再请求后端做一次精确校验 这样你既获得了本地快速过滤的好处，也保留了最终结果的准确性。布隆过滤器是怎么工作的 布隆过滤器的核心，其实就是一个 bit 数组。初始化时，所有 bit 都是 0。 原文用一组圆点把这些 bit 画了出来。为了便于说明，我们先假设这是一个只有 32 个 bit 的小型布隆过滤器。 往里插入一个元素时，过程分三步：用多个哈希函数对这个元素求哈希把每个哈希值对 bit 数组长度取模把得到的位置都置为 1 在原文的演示里，字符串 "foo" 会被这三个哈希函数处理：sha1sha256sha512 分别对 32 取模之后，会命中 bit 27、15 和 16。于是这三个位置被置为 1。 检查某个元素是否存在时，过程完全一样：用同样的哈希函数再算一遍找到对应的 bit 位检查这些位置是否全部已经是 1 于是：只要有任意一个位置还是 0，就能确定它一定没出现过如果所有位置都是 1，那它就可能出现过 这也直接带来两个后果。 第一，冲突是正常现象。不同元素命中同一个 bit，或者多个哈希函数刚好落在同一位置，都是允许发生的。 第二，随着越来越多 bit 被点亮，这个结构会逐渐失去区分能力。极端情况下，如果所有 bit 都变成 1，那么任何查询都会得到“也许存在”，此时这个布隆过滤器就几乎废掉了。假阳性率是怎么来的 布隆过滤器的假阳性率，和“数组里已经点亮了多少 bit”直接相关。 设：x 是当前已经置为 1 的 bit 比例k 是使用的哈希函数个数 那么一次查询误判为“可能存在”的概率，近似就是 x^k。 原文先从 k = 3 的情况讲起。假如一半的 bit 已经被点亮，也就是 x = 0.5，那么三次哈希都碰巧落到已点亮位置上的概率就是：0.5 * 0.5 * 0.5 = 0.125 也就是 12.5%。 这会让人很自然地产生一个念头：既然哈希函数越多，固定填充率下的假阳性率越低，那是不是哈希函数越多越好？ 答案是否定的。因为哈希函数越多，插入一个元素时点亮的 bit 也越多，布隆过滤器会更快被“填满”；同时，每次插入和查询都要额外计算更多哈希，CPU 成本也会上升。 所以哈希函数数量并不是越大越好，而是…