布隆过滤器

布隆过滤器

数据结构是个很有意思的东西，很多设计非常巧妙的数据结构能够大大降低某项操作的时间或者空间复杂度。所以我来开个专题来讲一些高级的，用途广泛的数据结构。搞数据结构专题的好处就是能够普及一些数据结构的原理和思想，第二个就是能够省下我很多考虑分享主题的时间。低级的数据结构，比如Hash，Set，链表队列之类的我就不讲了默认大家都会了。今天是第一篇，我们来讲讲布隆过滤器。

https://dl.acm.org/doi/10.1145/362686.362692(July, 1970)，这篇文章标志着布隆过滤器的诞生，有兴趣的同学可以去读一读。马上布隆过滤器就要过50岁的生日，讲布隆过滤器也算是老生常谈了。

什么是布隆过滤器？

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set."

• https://en.wikipedia.org/wiki/Bloom_filter

布隆过滤器是空间高效的概率型数据结构，是Burton Howard Bloom在1970年提出的，用于测试某个元素是否在一个集合中。布隆过滤器特点是，它有可能误判一个元素在当前集合中，但是不会误判这个元素不在集合中，换句话说，如果布隆过滤器告诉你当前元素在集合中，这个结论是有概率错误的，错误的概率称作误判（False Positive）率。但是如果它告诉你当前元素不在集合中，它一定是对的。再换句话说，布隆过滤器可以确定一个元素一定不存在或者可能存在于某个集合中

比如一种很典型的应用场景，我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些我们已经看过的内容。这里考虑下其它的数据结构，如果用HashMap或者Set来去重的话，所占用的空间就会非常大，因为我们对于每个用户都需要存多个新闻的ID。用Trie来存ID的话最后查询复杂度仍然会变成线性，没办法做到常数级。只要涉及到树形结构，查询的时间复杂度都是log级不是常数级。

所以布隆过滤器就是最适合这个场景的数据结构，它能在时间和空间复杂度上都做到常数级，在空间上还能比普通Hash结构节省 90% 以上。如果能容忍不精确判断的话，布隆过滤器是一个非常好用的去重数据结构。比如新闻场景中如果使用布隆过滤器，如果过滤器产生误判，这意味着用户可能看不到某个自己应该看到的新闻，这点影响对它带来的好处相比几乎可以忽略不计。

原理

S集合中有n个元素，利用k个哈希函数，将S中的每个元素映射到一个长度为m的位（bit）数组B中不同的位置上，这些位置上的二进制数均置为1，如果待检测的元素经过这k个哈希函数的映射后，发现其k个位置上的二进制数不全是1，那么这个元素一定不在集合S中，反之，该元素可能是S中的某一个元素

举例理解

我们用判断某个值是否在当前集合中来举一个例子，这里有个网站可以实际进行操作

1. 初始化一个8位bit空间

1. 假设三个hash函数 f(x), g(x), h(x)，对输入的数字进行计算并映射到对应位置 比如输入数字1，得到的值组合为 {1, 4, 8} ， 这是1这个数字对应在当前布隆过滤器中的指纹

1. 输入数字2，得到的值组合为 { 2, 4, 6 }

1. 检测4和5，对应的组合为 { 3, 6, 8 } 这时候发现第3个位置上是0，所以4一定不存在于集合中，

检测5 对应组合为 { 1 , 2 , 4} 发现位置1，2和4上都是1，则过滤器判断5 存在于集合当中，产生误判（False Positive）。

关于如何选取hash函数

• 散列函数之间不可以有相关关系
• 散列函数的值域必须在 1 - 8 之间，并且尽可能均匀

在实际生产中有现成的高效hash算法可以使用，比如FNV Hash

我们可以看到对于上述例子，布隆过滤器长度比较小，bit 位 1 所占比例的上升很快，当所有位都是1，那这个数据结构就完全失效了。

那么问题来了，我们如何选择布隆过滤器值域的大小？

时间和空间复杂度

具有False Positive风险的同时，布隆过滤器用来表示集合时，在空间占用上相对于其他一些数据结构（比如二叉平衡搜索树，前缀树，哈希表等）有非常明显的优势。大部分的数据结构最少也要存储数据本身的值。但是，布隆过滤器完全不用存储数据本身，它提供了一种分散式的解决办法。一个有1%误报率的布隆过滤器加上最优的hash函数的数量（k值），平均每个元素只需要占用9.6bit，并且跟所存储的数据自身大小无关。而且占用空间仅仅需要再加4.8bit/每个元素，就可以达到0.1%的误报率 由例子中的讨论可以得知，布隆过滤器在添加元素和检查某个元素是否在集合中这样的场景下的时间复杂度为O(k)，完全独立于集合中已经存在的元素数目。所有其它的固定集合大小的数据结构都没有这样的性质。而且布隆过滤器的k个hash函数完全不相关，比较适合硬件上的并行计算。误报率和占用空间的权衡 一般的布隆过滤器（比如redis）有两个参数，第一个是预计元素的数量 n（对应Redis中initial_size)，第二个是错误率 p(对应redis中的error_rate)。布隆过滤器根据这两个输入得到两个输出，第一个输出是位数组的长度 l，也就是需要的存储空间大小 (bit)，第二个输出是 hash 函数的最佳数量 k。hash 函数的数量也会直接影响到错误率，最佳的数量会有最低的错误率。

我们用公式帮助理解：（详细推导过程看 wiki ，大概是高数简单水平，仔细看也能看懂）

k=0.7*(l/n) 
p=0.6185^(l/n) 

从公式中可以看出：

1. 位数组相对越长 (l/n)，错误率 p 越低，这个和直观上理解是一致的
2. 位数组相对越长 (l/n)，hash 函数需要的最佳数量也越多，影响计算效率
3. 当一个元素平均需要 1 个字节 (8bit) 的指纹空间时 (l/n=8)，错误率大约为 2%
4. 错误率为 10%，一个元素需要的平均指纹空间为 4.792 个 bit，大约为 5bit
5. 错误率为 1%，一个元素需要的平均指纹空间为 9.585 个 bit，大约为 10bit
6. 错误率为 0.1%，一个元素需要的平均指纹空间为 14.377 个 bit，大约为 15bit

如果觉得计算比较麻烦，可以使用现成的网站 bloom-calculator

我们再来看当实际元素超出时错误率会发生什么变化？我们引入参数 t 表示实际元素和预计元素的倍数 t

p=(1-0.5^t)^k  # 极限近似，k 是 hash 函数的最佳数量

当 t 增大时，错误率 p 也会跟着增大，分别选择错误率为 10%,1%,0.1% 的 k 值，画出它的曲线进行直观观察:

由曲线可以看出，随着倍数增加错误率上升会非常大

1. 错误率为 10% 时，倍数比为 2 时，错误率就会升至接近 40%
2. 错误率为 1% 时，倍数比为 2 时，错误率升至 15%
3. 错误率为 0.1%，倍数比为 2 时，错误率升至 5%

当实际元素数量超过初始化数量时，应该对布隆过滤器进行 重建，重新分配一个 更大的过滤器，再将所有的历史元素批量添加。

其它用途

1. 布隆过滤器最常用于爬虫的URL过滤，爬虫通常有一个URL列表，保存着将要下载和已经下载的网页的URL，当它下载了一个网页，从网页中提取到新的URL后，需要判断该URL是否已经存在于列表中。此时，布隆过滤器是最好的选择。
2. 布隆过滤器可以与一些key-value的数据库一起使用，来加快查询。通常key-value存储系统的values存在硬盘，查询就是件费时的事。将Storage的数据都插入Filter，在Filter中查询都不存在时，那就不需要去Storage查询了。当误报出现时，只是会导致一次多余的Storage查询。由于布隆过滤器所用的空间非常小，所有可以常驻内存。这样子的话，对于大部分不存在的元素，我们只需要访问内存中的布隆过滤器就可以判断出来了，只有一小部分，我们需要访问在硬盘上的key-value数据库。从而大大地提高了效率。

代码实现

https://github.com/jasondavies/bloomfilter.js/blob/master/bloomfilter.js