LeetCode 算法专题深入布隆过滤器Bloom Filter的空间取舍、误报机制与 Java 实战【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文基于 leetcode 刷题仓库「算法专题」章节中的布隆过滤器讲义展开从10 亿访客判重的真实业务场景出发完整推导哈希表方案的空间瓶颈、bit 位图方案的演进逻辑、布隆过滤器bit 多个哈希函数的核心工作原理并给出可直接运行的 Java 实现与逐行解析。读完本篇你将掌握布隆过滤器可能存在 / 一定不存在的判定语义、误报率与空间参数的关系以及它背后的空间-准确率 trade-off 设计思想。上图直观展示了布隆过滤器的内部结构一个很长的二进制向量位数组加上多个哈希函数。输入经过 k 个哈希函数后在位向量的 k 个位置置 1查询时只要有一个位置为 0就断定元素不存在否则认为可能存在。一、问题场景10 亿访客的首次访问判定假设你运营一个网站拥有很多访客每当有用户访问时你想知道这个 IP 是不是第一次访问你的网站。1.1 显而易见的方案哈希表一个显而易见的答案是将所有的 IP 用 hashtable 存起来每次访问都去 hashtable 中取然后判断即可。但题目说了网站有很多访客。假如已有 10 亿个用户访问过假设 IP 是 IPv4那么每个 IP 的长度是 4 byte一共需要4 × 1000000000 4000000000 Bytes 4G仅仅是存储 IP 就要 4GB 内存。如果判断的是 URL 黑名单由于每个 URL 会更长可能远大于 IPv4 地址的 4 byte那么需要的空间可能会远远大于你的期望。核心矛盾当数据规模到十亿级时精确存储每一个元素的空间成本是不可接受的而我们需要回答的其实只是一个布尔问题——这个元素在不在集合里。既然只需要一个 bit 级的答案那么存储结构本身就可以被压缩。二、演进从哈希表到 bit 位图2.1 用 bit 表示存在 / 不存在另一个稍微难想到的解法是bit。我们知道 bit 有 0 和 1 两种状态那么用来表示存在与不存在再合适不过了。假如有 10 亿个 IP就可以用 10 亿个 bit 来存储1 × 1000000000 (4000000000 / 8) Bytes 128M空间变为原来的1/32如果是存储 URL 这种更长的字符串压缩效率会更高。问题随之而来我们怎么把 IPv4 和 bit 的位置关联上比如192.168.1.1应该用第几位表示10.18.1.1又该用第几位答案是使用哈希函数。基于这种想法我们只需要两个操作——set(ip)和has(ip)——以及一个内置函数hash(ip)用于将 IP 映射到 bit 表的某个位置。2.2 单哈希位表的两个致命缺点这样做有两个非常致命的缺点而它们的解法恰好指向了布隆过滤器当样本分布极度不均匀时会造成很大的空间浪费。我们可以通过优化散列函数来解决。当元素不是整型比如 URL时BitSet 就不适用了不能直接用 IP 数值本身当下标。我们还是可以使用散列函数来解决甚至可以多 hash 几次。第一个缺点的根源是一个元素占一个固定 bit造成了大量空洞第二个缺点的解法是让任意类型的元素都能通过哈希映射到位表下标。而多 hash 几次正是布隆过滤器的点睛之笔。三、布隆过滤器的工作原理bit 多个哈希函数布隆过滤器其实就是bit 多个散列函数。添加元素对元素做 k 次hash(ip)生成 k 个索引并将位向量上这 k 个索引位置的二进制置为 1。查询元素如果 k 个索引位置的值都为 1则认为其可能存在因为有哈希冲突的可能如果有一个不为 1那么它一定不存在——因为如果该元素曾被插入过它的 k 个哈希位置必然全部被置 1这是哈希函数确定性的保证。也就是说布隆过滤器回答了可能存在和一定不存在这两类问题。这正是它的全部语义边界位向量 k 个位置的状态判定结论可信度至少一个位置为 0一定不存在100% 可靠k 个位置全为 1可能存在有误报false positive可能从结构上看布隆过滤器本质上由一个很长的二进制向量和多个哈希函数组成见文首示意图。由于没有哈希表 100% 的可靠性这本质上是一种用可靠性换取空间的做法。除了可靠性之外布隆过滤器的删除也比较麻烦直接把某个元素的 k 个位置置 0可能会误伤其他共享了这些位的元素这是布隆过滤器的固有限制需要额外结构才能支持此处不展开。为什么多个哈希函数回到 2.2 节的两个缺点单个哈希函数下一个元素只占 1 个 bit冲突时无法区分多哈希之后每个元素由 k 个位置的指纹组合共同表示元素越独特它的指纹组合越难被其他元素的组合恰好覆盖——这就是误报率得以被压低、并且随元素总数 m 平滑增长的机制。同时多哈希也让任意类型元素如 URL 位表的组合成为可能直接解决了 BitSet 不能直接索引字符串的问题。四、误报False Positive与 Trade-off当布隆过滤器回答可能存在时你该怎么做一般而言为了宁可错杀一千也不放过一个比如安全黑名单、爬虫去重这类场景我们认为它存在。这个时候就产生了误报。几个关键事实讲义给出的结论误报率和二进制向量的长度成反比——位向量越长空间越大误报率越低在位向量长度和元素个数固定的前提下哈希函数个数 k 也存在一个使误报率最低的取值k 过小指纹太弱、k 过大位被 0 残留得越多作为行业通用结论补充若位向量长度为 m、已插入元素数为 n、哈希函数个数为 k误报率近似为(1 - e^(-kn/m))^k这也印证了误报率随 m 增大而指数级下降的讲义结论。因此布隆过滤器的工程价值可以一句话概括用可控的、可预估的误报率换取数量级上的空间节省。这就是讲义反复强调的 tradeoff取舍——从这个算法大家可以对取舍有更深的理解。适用性总结原文总结如果你需要判断一个元素是否在一个集合中出现过并且需要 100% 确定没有出现过或者接受可能出现过的模糊结论就可以考虑使用布隆过滤器。五、典型应用场景讲义列出了四类典型应用共同特征是海量集合 存在性查询 对误报容忍度尚可网络爬虫判断某个 URL 是否已经被爬取过爬虫 URL 队列动辄十亿级位图空间优势巨大K-V 数据库判断某个 key 是否存在比如 HBase 的每个 Region 中都包含一个 BloomFilter用于在查询时快速判断某个 key 在该 Region 中是否存在从而跳过无谓的磁盘 I/O钓鱼网站识别浏览器有时会警告用户访问的网站很可能是钓鱼网站用的就是这种技术本地只保存一份海量可疑域名的布隆过滤器查询零延迟恶意网站识别同理用于客户端快速过滤已知恶意域名。六、完整 Java 实现与逐行解析以下是讲义给出的完整实现MyBloomFilter用于判断可疑网站是否存在public class MyBloomFilter { private static final int DEFAULT_SIZE 2 31 ; private static final int[] seeds new int[] {3,5,7,11,13,19,23,37 }; private BitSet bits new BitSet(DEFAULT_SIZE); private SimpleHash[] func new SimpleHash[seeds.length]; public static void main(String[] args) { //使用 String value www.xxxxx.com ; MyBloomFilter filter new MyBloomFilter(); System.out.println(filter.contains(value)); filter.add(value); System.out.println(filter.contains(value)); } //构造函数 public MyBloomFilter() { for ( int i 0 ; i seeds.length; i ) { func[i] new SimpleHash(DEFAULT_SIZE, seeds[i]); } } //添加网站 public void add(String value) { for (SimpleHash f : func) { bits.set(f.hash(value), true ); } } //判断可疑网站是否存在 public boolean contains(String value) { if (value null ) { return false ; } boolean ret true ; for (SimpleHash f : func) { //核心就是通过“与”的操作 ret ret bits.get(f.hash(value)); } return ret; } }6.1 设计要点逐行解析seeds {3,5,7,11,13,19,23,37}8 个互不相同的种子值每个种子对应一个独立的哈希函数k 8。用不同种子派生多个哈希函数是工程上最常用的简化手段——每个SimpleHash用种子与元素哈希值做一次线性组合再取模种子不同则映射位置不同从而近似得到 k 个相互独立的哈希。add(value)对 8 个哈希函数逐一计算索引bits.set(index, true)将对应位置 1。注意它把true显式传入语义上就是只置 1不清 0——这也就呼应了前文说的删除困难。contains(value)用局部变量ret初始为true对 8 个位置做短路与运算ret ret bits.get(f.hash(value))。任何一个位置为 0ret立即变false并短路退出返回一定不存在8 个全为 1 才返回可能存在。这是整个布隆过滤器判定语义的核心一行。value null直接返回false防御性编程避免对 null 求哈希。SimpleHash讲义代码引用了辅助类SimpleHash(m, seed)它封装位表长度 m 种子 seedhash(value)返回[0, m)内的位索引。该辅助类在讲义中以独立小类的形式与MyBloomFilter配套出现一个常见的配套实现如下作为让上述代码可运行的补充供理解f.hash(value)的语义public class SimpleHash { private int seed; private int m; public SimpleHash(int m, int seed) { this.m m; this.seed seed; } public int hash(String value) { // 用种子派生不同的哈希结果先取字符串哈希 // 再与种子线性组合后对位表长度取模保证落在 [0, m) 内 return (value.hashCode() * seed) % m; } }6.2 一个需要注意的工程细节从源码结构看DEFAULT_SIZE 2 31在 Java 的 int 算术下会发生溢出2 31的高位被截断后等于Integer.MIN_VALUE-2147483648直接传给new BitSet(int nbits)会因负数抛IllegalArgumentException。讲义中这一常量意在表达一个非常大的位表规模实际落地时需要按业务规模显式选择一个正的位表长度例如对十亿级元素通常取2 302^31 个 bit约 256 MB量级并在插入量确定后按误报率公式反推 m 与 k 的合理取值。这一点不影响算法语义本身只影响能否原样编译运行。6.3 运行行为main中先查询www.xxxxx.com未插入输出falseadd之后再次查询输出true。注意true只是可能存在——对于恰好命中误报的 URL同样会返回true这是布隆过滤器的设计契约而非 bug。七、总结布隆过滤器回答了可能存在和一定不存在的问题。它本质是一种空间与准确率的取舍以位向量 多个哈希函数的结构把十亿级元素集合的存储从 GB 级压缩到 MB 级IP 场景下为原来的 1/32代价是引入可控的误报且不支持直接删除。实际使用可能会有误报的情况如果你的业务可以接受误报爬虫去重、缓存穿透防护、黑名单预过滤等那么使用布隆过滤器进行优化是一个不错的选择。延伸阅读本仓库内相关文档布隆过滤器中文版专题与本文对应的中文版本讲义算法专题总览本专题所在的算法专题章节索引包含滑动窗口、前缀树、位运算等相关内容书籍目录 与 仓库 README查看布隆过滤器在整本 leetcode 题解书籍中的位置图片源文件文首布隆过滤器原理示意图的原始图片。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 算法专题深入：布隆过滤器（Bloom Filter）的空间取舍、误报机制与 Java 实战
LeetCode 算法专题深入布隆过滤器Bloom Filter的空间取舍、误报机制与 Java 实战【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文基于 leetcode 刷题仓库「算法专题」章节中的布隆过滤器讲义展开从10 亿访客判重的真实业务场景出发完整推导哈希表方案的空间瓶颈、bit 位图方案的演进逻辑、布隆过滤器bit 多个哈希函数的核心工作原理并给出可直接运行的 Java 实现与逐行解析。读完本篇你将掌握布隆过滤器可能存在 / 一定不存在的判定语义、误报率与空间参数的关系以及它背后的空间-准确率 trade-off 设计思想。上图直观展示了布隆过滤器的内部结构一个很长的二进制向量位数组加上多个哈希函数。输入经过 k 个哈希函数后在位向量的 k 个位置置 1查询时只要有一个位置为 0就断定元素不存在否则认为可能存在。一、问题场景10 亿访客的首次访问判定假设你运营一个网站拥有很多访客每当有用户访问时你想知道这个 IP 是不是第一次访问你的网站。1.1 显而易见的方案哈希表一个显而易见的答案是将所有的 IP 用 hashtable 存起来每次访问都去 hashtable 中取然后判断即可。但题目说了网站有很多访客。假如已有 10 亿个用户访问过假设 IP 是 IPv4那么每个 IP 的长度是 4 byte一共需要4 × 1000000000 4000000000 Bytes 4G仅仅是存储 IP 就要 4GB 内存。如果判断的是 URL 黑名单由于每个 URL 会更长可能远大于 IPv4 地址的 4 byte那么需要的空间可能会远远大于你的期望。核心矛盾当数据规模到十亿级时精确存储每一个元素的空间成本是不可接受的而我们需要回答的其实只是一个布尔问题——这个元素在不在集合里。既然只需要一个 bit 级的答案那么存储结构本身就可以被压缩。二、演进从哈希表到 bit 位图2.1 用 bit 表示存在 / 不存在另一个稍微难想到的解法是bit。我们知道 bit 有 0 和 1 两种状态那么用来表示存在与不存在再合适不过了。假如有 10 亿个 IP就可以用 10 亿个 bit 来存储1 × 1000000000 (4000000000 / 8) Bytes 128M空间变为原来的1/32如果是存储 URL 这种更长的字符串压缩效率会更高。问题随之而来我们怎么把 IPv4 和 bit 的位置关联上比如192.168.1.1应该用第几位表示10.18.1.1又该用第几位答案是使用哈希函数。基于这种想法我们只需要两个操作——set(ip)和has(ip)——以及一个内置函数hash(ip)用于将 IP 映射到 bit 表的某个位置。2.2 单哈希位表的两个致命缺点这样做有两个非常致命的缺点而它们的解法恰好指向了布隆过滤器当样本分布极度不均匀时会造成很大的空间浪费。我们可以通过优化散列函数来解决。当元素不是整型比如 URL时BitSet 就不适用了不能直接用 IP 数值本身当下标。我们还是可以使用散列函数来解决甚至可以多 hash 几次。第一个缺点的根源是一个元素占一个固定 bit造成了大量空洞第二个缺点的解法是让任意类型的元素都能通过哈希映射到位表下标。而多 hash 几次正是布隆过滤器的点睛之笔。三、布隆过滤器的工作原理bit 多个哈希函数布隆过滤器其实就是bit 多个散列函数。添加元素对元素做 k 次hash(ip)生成 k 个索引并将位向量上这 k 个索引位置的二进制置为 1。查询元素如果 k 个索引位置的值都为 1则认为其可能存在因为有哈希冲突的可能如果有一个不为 1那么它一定不存在——因为如果该元素曾被插入过它的 k 个哈希位置必然全部被置 1这是哈希函数确定性的保证。也就是说布隆过滤器回答了可能存在和一定不存在这两类问题。这正是它的全部语义边界位向量 k 个位置的状态判定结论可信度至少一个位置为 0一定不存在100% 可靠k 个位置全为 1可能存在有误报false positive可能从结构上看布隆过滤器本质上由一个很长的二进制向量和多个哈希函数组成见文首示意图。由于没有哈希表 100% 的可靠性这本质上是一种用可靠性换取空间的做法。除了可靠性之外布隆过滤器的删除也比较麻烦直接把某个元素的 k 个位置置 0可能会误伤其他共享了这些位的元素这是布隆过滤器的固有限制需要额外结构才能支持此处不展开。为什么多个哈希函数回到 2.2 节的两个缺点单个哈希函数下一个元素只占 1 个 bit冲突时无法区分多哈希之后每个元素由 k 个位置的指纹组合共同表示元素越独特它的指纹组合越难被其他元素的组合恰好覆盖——这就是误报率得以被压低、并且随元素总数 m 平滑增长的机制。同时多哈希也让任意类型元素如 URL 位表的组合成为可能直接解决了 BitSet 不能直接索引字符串的问题。四、误报False Positive与 Trade-off当布隆过滤器回答可能存在时你该怎么做一般而言为了宁可错杀一千也不放过一个比如安全黑名单、爬虫去重这类场景我们认为它存在。这个时候就产生了误报。几个关键事实讲义给出的结论误报率和二进制向量的长度成反比——位向量越长空间越大误报率越低在位向量长度和元素个数固定的前提下哈希函数个数 k 也存在一个使误报率最低的取值k 过小指纹太弱、k 过大位被 0 残留得越多作为行业通用结论补充若位向量长度为 m、已插入元素数为 n、哈希函数个数为 k误报率近似为(1 - e^(-kn/m))^k这也印证了误报率随 m 增大而指数级下降的讲义结论。因此布隆过滤器的工程价值可以一句话概括用可控的、可预估的误报率换取数量级上的空间节省。这就是讲义反复强调的 tradeoff取舍——从这个算法大家可以对取舍有更深的理解。适用性总结原文总结如果你需要判断一个元素是否在一个集合中出现过并且需要 100% 确定没有出现过或者接受可能出现过的模糊结论就可以考虑使用布隆过滤器。五、典型应用场景讲义列出了四类典型应用共同特征是海量集合 存在性查询 对误报容忍度尚可网络爬虫判断某个 URL 是否已经被爬取过爬虫 URL 队列动辄十亿级位图空间优势巨大K-V 数据库判断某个 key 是否存在比如 HBase 的每个 Region 中都包含一个 BloomFilter用于在查询时快速判断某个 key 在该 Region 中是否存在从而跳过无谓的磁盘 I/O钓鱼网站识别浏览器有时会警告用户访问的网站很可能是钓鱼网站用的就是这种技术本地只保存一份海量可疑域名的布隆过滤器查询零延迟恶意网站识别同理用于客户端快速过滤已知恶意域名。六、完整 Java 实现与逐行解析以下是讲义给出的完整实现MyBloomFilter用于判断可疑网站是否存在public class MyBloomFilter { private static final int DEFAULT_SIZE 2 31 ; private static final int[] seeds new int[] {3,5,7,11,13,19,23,37 }; private BitSet bits new BitSet(DEFAULT_SIZE); private SimpleHash[] func new SimpleHash[seeds.length]; public static void main(String[] args) { //使用 String value www.xxxxx.com ; MyBloomFilter filter new MyBloomFilter(); System.out.println(filter.contains(value)); filter.add(value); System.out.println(filter.contains(value)); } //构造函数 public MyBloomFilter() { for ( int i 0 ; i seeds.length; i ) { func[i] new SimpleHash(DEFAULT_SIZE, seeds[i]); } } //添加网站 public void add(String value) { for (SimpleHash f : func) { bits.set(f.hash(value), true ); } } //判断可疑网站是否存在 public boolean contains(String value) { if (value null ) { return false ; } boolean ret true ; for (SimpleHash f : func) { //核心就是通过“与”的操作 ret ret bits.get(f.hash(value)); } return ret; } }6.1 设计要点逐行解析seeds {3,5,7,11,13,19,23,37}8 个互不相同的种子值每个种子对应一个独立的哈希函数k 8。用不同种子派生多个哈希函数是工程上最常用的简化手段——每个SimpleHash用种子与元素哈希值做一次线性组合再取模种子不同则映射位置不同从而近似得到 k 个相互独立的哈希。add(value)对 8 个哈希函数逐一计算索引bits.set(index, true)将对应位置 1。注意它把true显式传入语义上就是只置 1不清 0——这也就呼应了前文说的删除困难。contains(value)用局部变量ret初始为true对 8 个位置做短路与运算ret ret bits.get(f.hash(value))。任何一个位置为 0ret立即变false并短路退出返回一定不存在8 个全为 1 才返回可能存在。这是整个布隆过滤器判定语义的核心一行。value null直接返回false防御性编程避免对 null 求哈希。SimpleHash讲义代码引用了辅助类SimpleHash(m, seed)它封装位表长度 m 种子 seedhash(value)返回[0, m)内的位索引。该辅助类在讲义中以独立小类的形式与MyBloomFilter配套出现一个常见的配套实现如下作为让上述代码可运行的补充供理解f.hash(value)的语义public class SimpleHash { private int seed; private int m; public SimpleHash(int m, int seed) { this.m m; this.seed seed; } public int hash(String value) { // 用种子派生不同的哈希结果先取字符串哈希 // 再与种子线性组合后对位表长度取模保证落在 [0, m) 内 return (value.hashCode() * seed) % m; } }6.2 一个需要注意的工程细节从源码结构看DEFAULT_SIZE 2 31在 Java 的 int 算术下会发生溢出2 31的高位被截断后等于Integer.MIN_VALUE-2147483648直接传给new BitSet(int nbits)会因负数抛IllegalArgumentException。讲义中这一常量意在表达一个非常大的位表规模实际落地时需要按业务规模显式选择一个正的位表长度例如对十亿级元素通常取2 302^31 个 bit约 256 MB量级并在插入量确定后按误报率公式反推 m 与 k 的合理取值。这一点不影响算法语义本身只影响能否原样编译运行。6.3 运行行为main中先查询www.xxxxx.com未插入输出falseadd之后再次查询输出true。注意true只是可能存在——对于恰好命中误报的 URL同样会返回true这是布隆过滤器的设计契约而非 bug。七、总结布隆过滤器回答了可能存在和一定不存在的问题。它本质是一种空间与准确率的取舍以位向量 多个哈希函数的结构把十亿级元素集合的存储从 GB 级压缩到 MB 级IP 场景下为原来的 1/32代价是引入可控的误报且不支持直接删除。实际使用可能会有误报的情况如果你的业务可以接受误报爬虫去重、缓存穿透防护、黑名单预过滤等那么使用布隆过滤器进行优化是一个不错的选择。延伸阅读本仓库内相关文档布隆过滤器中文版专题与本文对应的中文版本讲义算法专题总览本专题所在的算法专题章节索引包含滑动窗口、前缀树、位运算等相关内容书籍目录 与 仓库 README查看布隆过滤器在整本 leetcode 题解书籍中的位置图片源文件文首布隆过滤器原理示意图的原始图片。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考