布隆过滤器（Bloom Filter）

raw/articles/2026/05/布隆过滤器

⚠️ 内容不完整提示：原文使用 JavaScript 动态加载，仅获取到 35 行简介，核心原理、实现代码、详细分析等内容缺失。

一句话总结

布隆过滤器的核心能力是：

• 在超大规模的数据集中，仅使用少量内存空间，即可快速判断一个元素是否存在。
• 具备数据隐私性。即，可以在不暴露具体数据的情况下，判断一个元素是否存在。

它的核心原理是，不存储具体数据，而仅仅存储数据指纹（哈希值），通过比对指纹来判断数据是否存在。

核心原理

布隆过滤器不存储具体数据，而仅仅存储数据指纹（哈希值），通过比对指纹来判断数据是否存在。

与哈希集合的对比：

特性	哈希集合	布隆过滤器
空间复杂度	$O(N)$	远低于 $O(N)$
数据存储	存储实际数据	仅存储哈希值（指纹）
数据隐私性	无（暴露实际数据）	有（不存储实际数据）
查询时间	$O(1)$	$O(1)$（多个哈希函数）
适用场景	数据规模较小	超大规模数据集

典型应用场景

1. 恶意 URL 检测：判断一个 HTTP 请求的 URL 是否在恶意 URL 列表中（列表可达上亿条），仅消耗少量内存和查询时间。

2. 大数据存储系统：为海量数据的多个文件各维护一个布隆过滤器，快速判断目标数据是否存在于该文件中，避免无效的磁盘 IO 操作。

前置知识

本文依赖以下基础知识（原文要求先学习）：

• 哈希表核心原理
• 位图核心原理及实现

关键要点

1. 空间效率极高：不存储实际数据，仅存储哈希值，空间消耗远低于哈希集合
2. 数据隐私保护：不暴露具体数据内容
3. 概率型数据结构：可能存在假阳性（false positive），但不存在假阴性（false negative）
4. 位图是基础组件：布隆过滤器使用位图（bitmap）作为底层存储结构

相关概念

• 布隆过滤器：布隆过滤器的定义、原理和应用场景
• 哈希表：对比参照
• 位图：布隆过滤器的基础组件，位图的定义、原理和应用场景

相关实体

• labuladong：算法学习平台作者