教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载布隆过滤器Bloom Filter是 Bloom 于 1970 年提出的一种基于多哈希函数映射的快速查找算法广泛用于海量数据处理场景中判断某元素是否属于集合且允许小概率误判的需求。本文以 Bloomfilter.md 为核心结合本仓库中 海量数据处理、Bitmap 与哈希表源码系统讲解其原理、应用场景、参数推导与可运行的代码实现。读完本文你将掌握布隆过滤器的时间/空间优势、误判率与位数组大小的数学关系并能在爬虫去重、Redis 缓存防穿透等场景中独立落地实践。一、为什么需要 Bloom Filter网络蜘蛛 URL 去重的困境假设要编写一个网络蜘蛛web crawler由于网络间链接错综复杂蜘蛛爬行很可能形成环。为了避免重复访问需要快速判断某个 URL 是否已经访问过。通常有四种方案存数据库将访问过的 URL 保存到数据库中存 HashSet将 URL 保存进 HashSet以接近 O(1) 的代价查询某个 URL 是否被访问过单向哈希后存储URL 经 MD5 或 SHA-1 等单向哈希后再保存到 HashSet 或数据库BitMap 方法建立一个 BitSet将每个 URL 经一个哈希函数映射到某一位。方案 1~3 都是把访问过的 URL完整保存方案 4 只标记 URL 的一个映射位。数据量较小时四种方案都能完美解决问题但数据量变得非常庞大后问题就来了方案 1 的缺点数据量庞大后关系型数据库的查询效率会变得很低而且每来一个 URL 就启动一次数据库查询代价过高方案 2 的缺点太消耗内存。随着 URL 增多占用内存越来越多——即使只有 1 亿个 URL、每个 URL 只算 50 个字符也需要5GB 内存方案 3 的改进字符串经 MD5 处理后的信息摘要长度只有 128 bitSHA-1 处理后也只有 160 bit因此比方案 2 节省好几倍内存方案 4 的局限消耗内存相对最少但单一哈希函数发生冲突的概率太高。若要降低冲突概率到 1%就需要将 BitSet 的长度设置为 URL 个数的100 倍。本质上上述算法都忽略了一个重要隐含条件允许小概率出错不一定要 100% 准确。比如少量 URL 实际没有被蜘蛛访问过却被误判为已访问代价很小——大不了少抓几个网页。这正是 Bloom Filter 存在的意义用可控的误判率换取内存的极大节省。与 Bitmap 的关联Bloom Filter 可以看作对 Bitmap 的扩展。本仓库 Bitmap.md 给出了 1-bit 标记元素是否存在的思路例如统计 8 位电话号码最多 99 999 999 个用 1 字节标记一个号码需要约 95MB而用 1 bit 标记只需 95/8 ≈ 12MB映射关系为a[k/8] | (0x01 (k%8))。Bloom Filter 正是沿用了1 个 bit 位标记取值0 或 1的位图思想再叠加多个哈希函数降低冲突概率。二、Bloom Filter 的典型应用场景1. 爬虫 URL 去重几个亿到几十亿的 URL 装入一个完整集合比较浪费空间把 URL 映射到布隆过滤器后一定是新 URL 的必定会被爬取少部分如 0.01%被误判为重复的 URL 可能其实是新 URL只会缺掉少量网页可接受。2. 垃圾邮件过滤把垃圾邮箱地址映射到 BloomFilter是垃圾邮箱的地址一定会被拦截绝不漏判代价只是一些正常邮箱被误伤给这些可怜的被误伤者设置白名单即可解决。3. 避免缓存穿透使用 BloomFilter 把所有数据放入 bit 数组用户请求时存在的值一定能放行部分不存在的值也会被放行但绝大部分会被拦截。典型案例如 DSP 广告系统通过设备 ID 读取用户信息key 为设备 idvalue 为用户信息 hashmap由于大量设备 id 都不是平台用户80% 以上Redis 中查不到用户信息会产生大量无效 Redis 读取用 BloomFilter 前置过滤可大幅减轻 Redis 读取压力。4. 减少磁盘 IOGoogle Bigtable、Apache HBase 使用 BloomFilter 防止不必要的磁盘 IO——先查内存中的 BloomFilter命中才真正访问磁盘。5. 减少网络请求 / 防攻击去重相同请求拦截即请求去重防止被攻击。6. Redis 4.0 布隆过滤器插件Redis 4.0 通过布隆过滤器插件支持主要有两个命令bf.add添加元素到布隆过滤器例如bf.add urls https://jaychen.ccbf.exists判断元素是否在过滤器中例如bf.exists urls https://jaychen.cc。7. 比特币 SPV 钱包BIP-37比特币 SPVSimple Payment Verification简单支付验证钱包应用中使用 BloomFilter 加速钱包同步主要用于移动支付场景——移动端不可能下载全节点数据几百 GB。在 2012 年 BIP-37 之前SPV 的做法是下载所有区块和交易然后在本地删除不相关的交易带来的问题是同步慢、浪费带宽、增加内存使用这也是当时用户对手机 APPBitcoin Wallet抱怨的原因。引入 BloomFilter 后保护隐私SPV 节点不用告诉相邻全节点自己所有钱包地址只说明一个可能存在于 bloomfilter 里的钱包地址集合高效过滤 UTXO通过 bloomfilter 过滤出可能属于钱包地址的 UTXO不在 bloomfilter 中地址对应的 UTXO 一定会被过滤掉不会漏掉自己的交易。三、Bloom Filter 核心算法Bloom Filter 由位图bitmap位数组和k 个哈希函数两部分组成。位图本质是一个 bit 位数组用一个 bit 位标记对应 Value 的取值0 或 1判断一个值是否存在就是看对应 bit 位是否为 1。插入过程使用 k 个哈希函数进行如下操作使用 k 个哈希函数对元素值进行 k 次计算得到 k 个哈希值根据得到的哈希值在位数组把对应下标的值置为 1。例如 URLhttps://jaychen.cc有 3 个哈希函数 f1、f2、f3 和一个位数组 arr对值进行三次哈希计算得到三个值 n1、n2、n3把位数组中 arr[n1]、arr[n2]、arr[n3] 置为 1。查询过程判断一个 URL 是否在布隆过滤器中对元素再次进行哈希计算得到值后判断位数组中每个对应元素是否都为 1存在一个值不为 1→ 该元素肯定不在布隆过滤器中所有位都为 1→ 该元素很大可能在布隆过滤器中不能 100% 确认。形式化算法描述创建 m 位的 bitset初始化为 0选中 k 个不同的哈希函数第 i 个哈希函数对字符串 str 哈希的结果记为 h(i, str)范围是 (0, m-1)记录字符串对 str 分别计算 h(1,str)、h(2,str)…h(k,str)将 bitset 的这 k 个位置置 1即一个 str 被映射到 bitset 的 k 个二进制位检查字符串是否存在分别计算 h(1,str)、h(2,str)…h(k,str)检查对应位是否为 1——若任何一位不为 1则 str一定没有被记录过若全部位都是 1则认为字符串存在但这并不能 100% 肯定因为该字符串对应的位可能恰好全被其他字符串置位这种误判称为false positive假阳性删除字符串字符串一旦加入就不能删除因为删除会影响其他字符串。实在需要删除时可以使用 Counting Bloom FilterCBF计数布隆过滤器。核心结论Bloom Filter 使用了 k 个哈希函数每个字符串与 k 个 bit 位对应从而大大降低了冲突概率。四、参数设计最优哈希函数个数与位数组大小哈希函数的选择哈希函数的选择对性能影响很大一个好的哈希函数应能近似等概率地将字符串映射到各个 bit 位。选择 k 个不同的哈希函数比较麻烦一种简单方法是只选一个哈希函数送入 k 个不同的参数即用参数区分出 k 个伪独立的哈希函数。最优参数公式设元素记录个数为 n、位数组大小bit 位数为 m则当满足k (ln2) * (m / n)时错误率最小。举一个常用取值假设错误率为 0.01此时 m 大约是 n 的13 倍k 大约是8 个。也就是说如果每个元素的原始长度远大于 13 个 bit约 1.6 字节使用 Bloom Filter 就能显著节省内存。这也是其以可控误判率换内存的量化依据元素本身越长、数量越多收益越明显。五、内存开销对比一个直观的工程案例本仓库 海量数据处理.md 中记录了两个可供量化的案例a、b 文件找共同 URL两个文件各存放 50 亿个 URL每个 URL 占 64 字节内存限制 4G。方案一采用hash 分而治之 hash_set方案二海量数据处理.md允许一定错误率时使用 Bloom Filter4G 内存大概可以表示 340 亿 bit将其中一个文件的 URL 映射为这 340 亿 bit再逐个读取另一个文件的 URL 检查是否命中命中即为共同 URL注意存在一定错误率Scrapy-Redis 去重机制一个 URL 指纹存储为 40 位 16 进制数如27adcc2e8979cdee0c9cecbbe8bf8ff51edefb61占用 20 Byte 内存空间1 亿个指纹占用 2 GB——这正是完整存储方案的内存代价也是布隆过滤器用武之地。六、实现示例C 与 Java 双语言实战C 风格示例位数组 种子哈希函数#define SIZE 15*1024*1024 char a[SIZE]; /* 15MB*8 120M bit空间 */ memset(a,0,SIZE); int seeds[] { 5, 7, 11, 13, 31, 37, 61}; int hashcode(int cap,int seed, string key){ int hash 0; for (int i0;ikey.length();i){ hash (seed*hash key.charAt(i)); } return hash (cap-1); }对每个字符串 str 求哈希即可使用hashcode(SIZE*8, seeds[i], str)其中 i 的取值范围是 (0, k)。hash (cap-1)是位运算取模技巧当容量 cap 为 2 的幂时cap-1等价于掩码取 hash 的低位作为下标比取模运算快得多。这一点与仓库中哈希表实现一脉相承——hash_ref.c 使用hash (hashMap-sizeForIndex)计算桶下标HashMap in Java.md 中同样采用h (length-1)定位桶并指出位与运算比取模运算快约 10 倍。Java 示例单哈希函数 不同种子派生多哈希public class Hash { private static int[] hashSeeds new int[]{33, 53, 79, 97, 113, 137, 163, 181}; /** * 一组哈希用同一哈希函数配合 8 个不同种子得到 8 个伪独立哈希值 */ public static int[] hashes(String key, int slots) { int[] hs new int[8]; for (int i 0; i hs.length; i) { hs[i] Hash.hash(key, i) % slots; } return hs; } /** * 单个哈希DJBP 风格种子×累加 */ public static int hash(String key, int index) { int h 5381; for (int i 0; i key.length(); i) { h hashSeeds[index] * h key.charAt(i); } return (h ^ (h 16)) Integer.MAX_VALUE; } }这段代码正好呼应上文选一个哈希函数、送入 k 个不同参数的建议hashSeeds数组提供 8 个种子hash(key, index)用不同种子派生出 8 个不同的哈希值(h ^ (h 16))让高 16 位与低 16 位混合改善分布均匀性与 Java HashMap 中(h key.hashCode()) ^ (h 16)的扰动思想一致见 HashMap in Java.md。Java 示例基于 ByteBuffer 的布隆过滤器本体public class ByteBufferBloomFilter { /** * 存储BloomFilter数据 */ private final ByteBuffer data; private final int size;//占用空间 /** * 构造BloomFilter * param size 占用空间字节数应设为key总数的1.5倍以上最大不超过2G */ public ByteBufferBloomFilter(int size) { if (size 0) { throw new IllegalArgumentException(size must 0); } this.size size; this.data ByteBuffer.allocateDirect(size); } Override public void put(String key) { int[] hs Hash.hashes(key, size); for (int i 0; i hs.length; i) { int idx hs[i]; int b data.get(idx); data.put(idx, (byte) (b | (1 i))); } } Override public boolean contains(String key) { int[] hs Hash.hashes(key, size); for (int i 0; i hs.length; i) { int b data.get(hs[i]); if ((b (1 i)) 0) { return false; } } return true; } Override public int size() { return size; } }实现要点构造ByteBuffer.allocateDirect(size)分配堆外内存注释给出关键工程参数——占用空间应设为 key 总数的 1.5 倍以上最大不超过 2Gput对 key 计算 8 个哈希值逐个将对应字节的对应 bit 置 1b | (1 i)contains逐个检查 8 个哈希位置的 bit任何一个为 0 即返回 false肯定不存在全部为 1 才返回 true可能存在完整实现了一票否决、全 1 才疑似存在的判定逻辑注意size的单位是字节而Hash.hashes返回的下标直接按字节取因此哈希结果被限制在字节数范围内而非 bit 位范围内——工程上以字节为粒度实现位图是常见做法代价是位粒度更粗。七、局限性与演进方向不能删除字符串一旦加入就不能删除因为删除会影响其他字符串多个元素共享同一 bit 位存在假阳性查询时全部位为 1只能说明很可能存在无法 100% 确认假阳性率为 0绝不漏判只可能误报凡是判定不在的元素一定不在集合中这一特性正是垃圾邮件拦截等场景可用性的保证需要删除的场景使用 Counting Bloom FilterCBF把每个 bit 扩展为计数器删除时做减计数。八、延伸阅读与仓库导航布隆过滤器是海量数据处理技术栈的重要一环本仓库 海量数据处理 将其与 Bitmap、Hash 映射分而治之、Trie 树、倒排索引.md)、外排序、simhash 等并列组成海量数据处理工具箱。理解布隆过滤器背后的哈希与位图思想可进一步阅读Bitmap.md位图数据结构基础1 bit 标记元素存在性的核心思路海量数据处理.md340 亿 bit 方案、2-Bitmap 找不重复整数等实战题目HashMap in Java.md 与 hash_ref.c哈希函数的扰动、位运算取模、冲突处理等底层细节布隆过滤器在开源系统中的落地本仓库 Bitcoin 目录 记录了 Merkle Tree 等比特币相关数据结构可作为理解 SPV 钱包场景的延伸材料。综上布隆过滤器的工程价值在于用可控的小概率误判换取数量级的内存节省与 O(k) 级别的查询时间复杂度。在爬虫去重、缓存防穿透、垃圾邮件过滤、HBase/Bigtable 磁盘 IO 优化以及比特币 SPV 钱包同步等场景中它都是经过大规模生产验证的高性价比方案。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐iCloud照片下载器完整指南一次配好7个场景iCloud照片下载器完整指南一次配好7个场景 照片视频都堆在 iCloud本地硬盘上却没有一份完整备份icloud_photos_downloaderCLIvLLM隐藏状态服务实战Switchyard本地模型Prefill特征提取完整指南vLLM隐藏状态服务实战Switchyard本地模型Prefill特征提取完整指南 Switchyard 是一款让 LLM 应用跨模型、跨供应商智能分流的开源人工智能大模型LLM 网关模型路由如何快速安装CanteraWindows/Linux/macOS系统安装教程如何快速安装CanteraWindows/Linux/macOS系统安装教程 Cantera是一款强大的化学动力学、热力学和传输工具套件支持多平台安装。本文科学计算高性能计算上一篇RapidOCR Python API全解析从入门到企业级应用下一篇Talebook安全配置指南防止非法访问的关键设置创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考