【算法】——布隆过滤器

快来打我* 2022-04-24 01:32 162阅读 0赞

### 前言 ###

在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用哈希表，每存储一亿个 email 地址， 就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的。  
今天，我们介绍一种称作布隆过滤器的数学工具，它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。

### 一、Hash函数 ###

Hash，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。 这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能 会散列成相同的输出，而不可能从散列值来唯一的确定输入值。数学表述为：h = H(M) ， 其中H( )--单向散列函数，M--任意长度明文，h--固定长度散列值。

[![1538113681-9665-313836373034343032312e706e67.png][]][1538113681-9665-313836373034343032312e706e67.png]

数据本身则可以通过一个hash函数计算出一个key，这个key是一个位置，而这个key所对的值就是0或者1（因为只有两种状态）。

### 二、布隆过滤器原理 ###

上面的思路其实就是布隆过滤器的思想，只不过因为hash函数的限制，多个字符串很可能会hash成一个值。为了解决这个问题，布隆过滤器引入多个hash函数来降低误判率。下图表示有三个hash函数，比如一个集合中有x，y，z三个元素，分别用三个hash函数映射到二进制序列的某些位上，假设我们判断w是否在集合中，同样用三个hash函数来映射，结果发现取得的结果不全为1，则表示w不在集合里面。

[![1538113736-2965-4360245-015a6e823496b8b3.png][]][1538113736-2965-4360245-015a6e823496b8b3.png]

### 三、布隆过滤器处理流程 ###

布隆过滤器应用很广泛，比如垃圾邮件过滤，爬虫的url过滤，防止缓存击穿等等。下面就来说说布隆过滤器的一个完整流程，相信读者看到这里应该能明白布隆过滤器是怎样工作的。

**第一步：开辟空间**

开辟一个长度为m的位数组（或者称二进制向量），这个不同的语言有不同的实现方式，甚至你可以用文件来实现。

**第二步：寻找hash函数**

获取几个hash函数，前辈们已经发明了很多运行良好的hash函数，比如BKDRHash，JSHash，RSHash等等。这些hash函数我们直接获取就可以了。

**第三步：写入数据**

将所需要判断的内容经过这些hash函数计算，得到几个值，比如用3个hash函数，得到值分别是1000，2000，3000。之后设置m位数组的第1000，2000，3000位的值位二进制1。

**第四步：判断**

接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的。

### **四、查询元素** ###

查询W元素是否存在集合中的时候，同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。反之，如果3个点都为1，则该元素**可能**存在集合中。注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。可以从图中可以看到：假设某个元素通过映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。

### **五、移除集合中的元素** ###

这个在布隆过滤器中是**不允许**的，理解原理我们就知道，如果将是1的位置重置成0会影响其他元素是不是在集合中的判断。对于关小黑屋再放出来这种需求，我们可以换一个思路，再加一个布隆过滤器————“被移除的元素”，当然现在公司都比较土豪，直接用redis存一个过期时间就可以，那就不在我们讨论之列了，**布隆过滤器的初衷是用少许的误判来极大的节省空间**。

## **六、错误率** ##

假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位，假定由每个 Hash 计算出需要设置的位（bit） 的位置是相互独立, m 是该位数组的大小，k 是 Hash 函数的个数. 位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是：

![1620][]

在所有 k 次 Hash 操作后该位都没有被置 "1" 的概率是：

![1620 1][]

如果我们插入了 n 个元素，那么某一位仍然为 "0" 的概率是：

![1620 2][]

该位为 "1"的概率是：

![1620 3][]

检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 "1"，但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中（False Positives），该概率由以下公式确定：

![1620 4][]

如何使得错误率最小，对于给定的m和n，当 k=m/n \* ln2 的时候取值最小。关系如下图所示：

![1620 5][]

### 七、总结 ###

Bloom Filter实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率（假正例False positives，即Bloom Filter报告某一元素存在于某集合中，但是实际上该元素并不在集合中）和删除困难，但是没有识别错误的情形（即假反例False negatives，如果某个元素确实在该集合中，那么Bloom Filter 是不会报告该元素不存在于集合中的，所以不会漏报）。

【参考文章】

参考文章1：[https://cloud.tencent.com/developer/article/1358438][https_cloud.tencent.com_developer_article_1358438]

参考文章2：[http://imhuchao.com/1271.html][http_imhuchao.com_1271.html]

[1538113681-9665-313836373034343032312e706e67.png]: /images/20220221/edc6c69e029a4dcc83f87226cb75b29f.png
[1538113736-2965-4360245-015a6e823496b8b3.png]: /images/20220221/ba363ee2ae0740fc92765c5b741adeaf.png
[1620]: https://ask.qcloudimg.com/http-save/yehe-3106926/xuokqa5p8o.png?imageView2/2/w/1620
[1620 1]: https://ask.qcloudimg.com/http-save/yehe-3106926/vc0ajk6fhj.png?imageView2/2/w/1620
[1620 2]: https://ask.qcloudimg.com/http-save/yehe-3106926/zl3jj9nial.png?imageView2/2/w/1620
[1620 3]: https://ask.qcloudimg.com/http-save/yehe-3106926/r76ck4m1zo.png?imageView2/2/w/1620
[1620 4]: https://ask.qcloudimg.com/http-save/yehe-3106926/ddsyqm230u.png?imageView2/2/w/1620
[1620 5]: https://ask.qcloudimg.com/http-save/yehe-3106926/bs5jr2o105.jpeg?imageView2/2/w/1620
[https_cloud.tencent.com_developer_article_1358438]: https://cloud.tencent.com/developer/article/1358438
[http_imhuchao.com_1271.html]: http://imhuchao.com/1271.html