企业官网建设流程全解析

• 教程

布隆过滤器（Bloom Filter）是 Bloom 于 1970 年提出的一种基于多哈希函数映射的快速查找算法，广泛用于海量数据处理场景中"判断某元素是否属于集合"且允许小概率误判的需求。本文以 Bloomfilter.md 为核心，结合本仓库中 海量数据处理、Bitmap 与哈希表源码，系统讲解其原理、应用场景、参数推导与可运行的代码实现。读完本文，你将掌握布隆过滤器的时间/空间优势、误判率与位数组大小的数学关系，并能在爬虫去重、Redis 缓存防穿透等场景中独立落地实践。

一、为什么需要 Bloom Filter：网络蜘蛛 URL 去重的困境

假设要编写一个网络蜘蛛（web crawler），由于网络间链接错综复杂，蜘蛛爬行很可能形成"环"。为了避免重复访问，需要快速判断"某个 URL 是否已经访问过"。通常有四种方案：

1. 存数据库：将访问过的 URL 保存到数据库中；
2. 存 HashSet：将 URL 保存进 HashSet，以接近 O(1) 的代价查询某个 URL 是否被访问过；
3. 单向哈希后存储：URL 经 MD5 或 SHA-1 等单向哈希后再保存到 HashSet 或数据库；
4. BitMap 方法：建立一个 BitSet，将每个 URL 经一个哈希函数映射到某一位。

方案 1~3 都是把访问过的 URL完整保存，方案 4 只标记 URL 的一个映射位。数据量较小时四种方案都能完美解决问题，但数据量变得非常庞大后问题就来了：

• 方案 1 的缺点：数据量庞大后关系型数据库的查询效率会变得很低，而且每来一个 URL 就启动一次数据库查询代价过高；
• 方案 2 的缺点：太消耗内存。随着 URL 增多，占用内存越来越多——即使只有 1 亿个 URL、每个 URL 只算 50 个字符，也需要5GB 内存；
• 方案 3 的改进：字符串经 MD5 处理后的信息摘要长度只有 128 bit，SHA-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 为设备 id，value 为用户信息 hashmap），由于大量设备 id 都不是平台用户（80% 以上），Redis 中查不到用户信息，会产生大量无效 Redis 读取；用 BloomFilter 前置过滤可大幅减轻 Redis 读取压力。

4. 减少磁盘 IO

Google Bigtable、Apache HBase 使用 BloomFilter 防止不必要的磁盘 IO——先查内存中的 BloomFilter，命中才真正访问磁盘。

5. 减少网络请求 / 防攻击去重

相同请求拦截，即请求去重，防止被攻击。

6. Redis 4.0 布隆过滤器插件

Redis 4.0 通过布隆过滤器插件支持，主要有两个命令：

• bf.add：添加元素到布隆过滤器，例如bf.add urls https://jaychen.cc；
• bf.exists：判断元素是否在过滤器中，例如bf.exists urls https://jaychen.cc。

7. 比特币 SPV 钱包（BIP-37）

比特币 SPV（Simple Payment Verification，简单支付验证）钱包应用中使用 BloomFilter 加速钱包同步，主要用于移动支付场景——移动端不可能下载全节点数据（几百 GB）。

在 2012 年 BIP-37 之前，SPV 的做法是下载所有区块和交易，然后在本地删除不相关的交易，带来的问题是同步慢、浪费带宽、增加内存使用，这也是当时用户对手机 APP"Bitcoin Wallet"抱怨的原因。引入 BloomFilter 后：

• 保护隐私：SPV 节点不用告诉相邻全节点自己所有钱包地址，只说明一个"可能存在于 bloomfilter 里的钱包地址集合"；
• 高效过滤 UTXO：通过 bloomfilter 过滤出可能属于钱包地址的 UTXO，不在 bloomfilter 中地址对应的 UTXO 一定会被过滤掉（不会漏掉自己的交易）。

三、Bloom Filter 核心算法

Bloom Filter 由位图（bitmap）位数组和k 个哈希函数两部分组成。位图本质是一个 bit 位数组，用一个 bit 位标记对应 Value 的取值（0 或 1）；判断一个值是否存在，就是看对应 bit 位是否为 1。

插入过程

使用 k 个哈希函数进行如下操作：

1. 使用 k 个哈希函数对元素值进行 k 次计算，得到 k 个哈希值；
2. 根据得到的哈希值，在位数组把对应下标的值置为 1。

例如 URLhttps://jaychen.cc，有 3 个哈希函数 f1、f2、f3 和一个位数组 arr：

• 对值进行三次哈希计算，得到三个值 n1、n2、n3；
• 把位数组中 arr[n1]、arr[n2]、arr[n3] 置为 1。

查询过程

判断一个 URL 是否在布隆过滤器中：对元素再次进行哈希计算，得到值后判断位数组中每个对应元素是否都为 1：

• 存在一个值不为 1→ 该元素肯定不在布隆过滤器中；
• 所有位都为 1→ 该元素很大可能在布隆过滤器中（不能 100% 确认）。

形式化算法描述

1. 创建 m 位的 bitset，初始化为 0，选中 k 个不同的哈希函数；
2. 第 i 个哈希函数对字符串 str 哈希的结果记为 h(i, str)，范围是 (0, m-1)；
3. 记录字符串：对 str 分别计算 h(1,str)、h(2,str)…h(k,str)，将 bitset 的这 k 个位置置 1，即一个 str 被映射到 bitset 的 k 个二进制位；
4. 检查字符串是否存在：分别计算 h(1,str)、h(2,str)…h(k,str)，检查对应位是否为 1——若任何一位不为 1，则 str一定没有被记录过；若全部位都是 1，则"认为"字符串存在，但这并不能 100% 肯定，因为该字符串对应的位可能恰好全被其他字符串置位，这种误判称为false positive（假阳性）；
5. 删除字符串：字符串一旦加入就不能删除，因为删除会影响其他字符串。实在需要删除时可以使用 Counting Bloom Filter（CBF，计数布隆过滤器）。

核心结论：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 中记录了两个可供量化的案例：

1. a、b 文件找共同 URL：两个文件各存放 50 亿个 URL，每个 URL 占 64 字节，内存限制 4G。方案一采用"hash 分而治之 + hash_set"；方案二（海量数据处理.md）允许一定错误率时使用 Bloom Filter：4G 内存大概可以表示 340 亿 bit，将其中一个文件的 URL 映射为这 340 亿 bit，再逐个读取另一个文件的 URL 检查是否命中，命中即为共同 URL（注意存在一定错误率）；
2. 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 i=0;i<key.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 倍以上，最大不超过 2G；
• put：对 key 计算 8 个哈希值，逐个将对应字节的对应 bit 置 1（b | (1 << i)）；
• contains：逐个检查 8 个哈希位置的 bit，任何一个为 0 即返回 false（肯定不存在），全部为 1 才返回 true（可能存在），完整实现了"一票否决、全 1 才疑似存在"的判定逻辑；
• 注意size的单位是字节，而Hash.hashes返回的下标直接按字节取，因此哈希结果被限制在字节数范围内，而非 bit 位范围内——工程上以"字节"为粒度实现位图是常见做法，代价是位粒度更粗。

七、局限性与演进方向

• 不能删除：字符串一旦加入就不能删除，因为删除会影响其他字符串（多个元素共享同一 bit 位）；
• 存在假阳性：查询时"全部位为 1"只能说明"很可能存在"，无法 100% 确认；
• 假阳性率为 0（绝不漏判，只可能误报）：凡是"判定不在"的元素一定不在集合中，这一特性正是垃圾邮件拦截等场景可用性的保证；
• 需要删除的场景：使用 Counting Bloom Filter（CBF），把每个 bit 扩展为计数器，删除时做减计数。

八、延伸阅读与仓库导航

布隆过滤器是海量数据处理技术栈的重要一环，本仓库 海量数据处理 将其与 Bitmap、Hash 映射，分而治之、Trie 树、倒排索引.md)、外排序、simhash 等并列组成"海量数据处理工具箱"。理解布隆过滤器背后的哈希与位图思想，可进一步阅读：

• Bitmap.md：位图数据结构基础，1 bit 标记元素存在性的核心思路；
• 海量数据处理.md：340 亿 bit 方案、2-Bitmap 找不重复整数等实战题目；
• HashMap in Java.md 与 hash_ref.c：哈希函数的扰动、位运算取模、冲突处理等底层细节；
• 布隆过滤器在开源系统中的落地：本仓库 Bitcoin 目录 记录了 Merkle Tree 等比特币相关数据结构，可作为理解 SPV 钱包场景的延伸材料。

综上，布隆过滤器的工程价值在于：用可控的小概率误判，换取数量级的内存节省与 O(k) 级别的查询时间复杂度。在爬虫去重、缓存防穿透、垃圾邮件过滤、HBase/Bigtable 磁盘 IO 优化以及比特币 SPV 钱包同步等场景中，它都是经过大规模生产验证的高性价比方案。

• 教程