BloomFilter算法知识点 _BloomFilter算法

1.介绍BloomFilter（布隆过滤器）是一种可以高效地判断元素是否在某个集合中的算法。
在很多日常场景中，都大量存在着布隆过滤器的应用。例如：检查单词是否拼写正确、网络爬虫的URL去重、黑名单检验，微博中昵称不能重复的检测。在工业界中， google著名的分布式数据库BigTable也用
了布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数；Google Chrome浏览器使用BloomFilter来判断一个网站是否为恶意网站。
对于以上场景，可能很多人会说，用HashSet甚至简单的链表、数组做存储，然后判断是否存在不就可以了吗？
当然，对于少量数据来说， HashSet是很好的选择。但是对于海量数据来说， BloomFilter相比于其他数据结构在空间效率和时间效率方面都有着明显的优势。
但是，布隆过滤器具有一定的误判率，有可能会将本不存在的元素判定为存在。因此，对于那些需要“零错误”的应用场景，布隆过滤器将不太适用。具体的原因将会在第二部分中介绍。
在本文的第二部分，本文将会介绍BloomFilter的基本算法思想；第三部分将会基于Google开源库Guava来讲解BloomFilter的具体实现；在第四部分中，将会介绍一些开源的BloomFilter的扩展，以解决目前BloomFilter的不足。
2.算法讲述布隆过滤器是基于Hash来实现的，在学习BloomFilter之前，也需要对Hash的原理有基本的了解。个人认为， BloomFilter的总体思想实际上和bitmap很像，但是比bitmap更节省空间，误判率也更低。
BloomFilter的整体思想并不复杂，主要是使用k个Hash函数将元素映射到位向量的k个位置上面，并将这k个位置全部置为1 。当查找某元素是否存在时，查找该元素所对应的k位是否全部为1即可说明该元素是否存在。
2.1算法流程
BloomFilter的整体算法流程可总结为如下步骤：

BloomFilter初始化为m位长度的位向量，每一位均初始化为0

文章插图

使用k个相互独立的Hash函数，每个Hash函数将元素映射到{1..m}的范围内，并将对应的位置为1 。

文章插图

如上图所示，元素x分别被三个Hash函数映射到了三个位置8、1、14 ，并将这三个位置从0变为1 。
若检查一个元素y是否存在，首先第一步使用k个Hash函数将元素y映射到k位。分别检测每一位是否为0 。若某一位为0 ，则元素y一定不存在，若全部为1 ，则有可能存在。

2.2空间复杂度
BloomFilter 使用位向量来表示元素，而不存储本身，这样极大压缩了元素的存储空间。其空间复杂度为O(m) ， m是位向量的长度。而m与插入总数量n的关系如公式

文章插图

我们可以利用这个公式来算一下需要抓取100万个URL时BloomFilter所占据的空间。
假设要求误判率为1% ，因此该公式可转化为m=9.6∗n
。故此时BloomFilter位向量的大小为100w∗9.6=960wbit
，约1.1M内存空间。
只需要1.1M的内存空间，就可满足100万个url的去重需求，这个空间复杂度之低不可谓不惊人。
实际上，哪怕是1亿个URL ，也仅需100M左右的内存空间即可满足BloomFilter的空间需求，这对于绝大部分爬虫的体量来说，是完全可行的。
1MB ≈ 10^3KB ≈ 10^6Byte ≈ 8 * 10^6b = 800Wbit
2.3时间复杂度
时间复杂度方面 BloomFilter的时间复杂度仅与Hash函数的个数k有关，即O(k)
2.4缺点
删除元素
BloomFilter 由于并不存储元素，而是用位的01来表示元素是否存在，并且很有可能一个位时被多个元素同时使用。所以无法通过将某元素对应的位置为0来删除元素。
幸运的是，目前学术界和工业界都有很多方法扩展已解决以上问题。
强烈建议读取下面两篇文章，并且把其中的公式推导一遍：