布隆过滤器

1. 使用场景

• 在使⽤word⽂档时，word如何判断某个单词是否拼写正确.
• ⽹络爬⾍程序，怎么让它不去爬相同的url⻚⾯？允许有误差.
• 垃圾邮件（短信）过滤算法如何设计？允许有误差.
• 公安办案时，如何判断某嫌疑⼈是否在⽹逃名单中？控制误差 假阳率.
• 缓存穿透问题如何解决？允许有误差.

2. 基本思想

可以通过多个Hash函数将元素映射成位图中的数个点，将这些点标记为true，在查询的时候，通过查询这些点是否为true，就可以判断布隆过滤器中是否存在这个元素.所以布隆过滤器相⽐传统的查询结构（例如：hash，set，map等数据结构）更加⾼效，占⽤空间更
⼩.

注意：

• 布隆过滤器无法删除元素，因为它不存储具体的元素，只存储元素映射成的数个点，而且每个点可能被多个元素映射的结果所覆盖.
• 布隆过滤器只能判断一个元素不存在或者可能存在，当使用hash函数映射出的所有点都为true时，该元素可能存在，只要有一个不为true，就必定不存在.

3. 布隆过滤器的实现

组成

位图（bit数组）+ n个hash函数.

原理

当⼀个元素加⼊位图时，通过k个hash函数将这个元素映射到位图的k个点，并把它们置为1；当检索时，再通过k个hash函数运算检测位图的k个点是否都为1；如果有不为1的点，那么认为不存在；如果全部为1，则可能存在（存在误差）.

在位图中每个槽位只有两种状态（0或者1），⼀个槽位被设置为1状态，但不明确它被设置了多少次；也就是不知道被多少个str1哈希映射以及是被哪个hash函数映射过来的；所以不⽀持删除操作.

4. 布隆过滤器的设计

在实际应⽤过程中，布隆过滤器该如何使⽤？要选择多少个hash函数，要分配多少空间的位图，存
储多少元素？另外如何控制假阳率（布隆过滤器能明确⼀定不存在，不能明确⼀定存在，那么存在
的判断是有误差的，假阳率就是错误判断存在的概率）？

我们一般使用以下四个参数来解决上面的问题：

• n – 布隆过滤器中元素的个数，如上图 只有str1和str2 两个元素 那么 n=2.
• p – 假阳率，在0-1之间 0.000000.
• m – 位图所占空间.
• k – hash函数的个数.

公式如下：

n = ceil(m / (-k / log(1 - exp(log(p) / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log(p)) / log(1 / pow(2, log(2))))
k = round((m / n) * log(2))
1
2
3
4

其中下面的两个参数m和k由上面两个参数n和p计算得到，可以自己计算，也可以在相关的网站上输入前两个值然后计算后两个值：

https://hur.st/bloomfilter/

k个hash函数

上述计算结果中，k=23 ，在实际中，我们不会真的去选择23个hash函数，而是采用双重hash的方式去模拟出23个hash函数：

// 采⽤⼀个hash函数，给hash传不同的种⼦偏移值
// #define MIX_UINT64(v) ((uint32_t)((v>>32)^(v)))
uint64_t hash1 = MurmurHash2_x64(key, len, Seed);
uint64_t hash2 = MurmurHash2_x64(key, len, MIX_UINT64(hash1));
for (i = 0; i < k; i++) // k 是hash函数的个数
{
   Pos[i] = (hash1 + i*hash2) % m; // m 是位图的⼤⼩
}
1
2
3
4
5
6
7
8