布隆过滤器问题

概念介绍

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

布隆过滤器的特征是：它可以判断某个数据一定不存在，但是无法判断一定存在。（确实有点拗口，但当我们介绍完它的原理，就很容易明白了）

使用场景

场景一

原本有10亿个号码，现在又来了10万个号码，如何快速判断这10万个号码是否在10亿个号码库中？

场景二

需要爬虫的网站千千万万，对于一个新的网站url，我们如何判断这个url我们是否已经爬过了？

解决方案

针对上面的需求，我们一般会想到两种解决方案：

方案一：将10亿个号码存入数据库中，进行数据库查询，准确性有了，但是速度会比较慢。

方案二：将10亿号码放入内存中，比如Redis缓存中，这里我们算一下占用内存大小：10亿*8字节=8GB，通过内存查询，准确性和速度都有了，但是大约8GB的内存空间，挺浪费内存空间的。

那么对于类似这种，海量数据集合，如何准确快速的判断某个数据是否在大数据量集合中，并且不占用内存？那么布隆过滤器应运而生了。

实现原理

布隆过滤器是什么？

它是一种数据结构，是由一串很长的二进制向量组成，也可以将其看成一个二进制数组。既然是二进制，那么里面存放的不是0，就是1，但是初始默认值都是0。

如下图所示：

添加数据如何处理？

当要插入一个元素时，将其数据分别输入k个哈希函数，产生k个哈希值。以哈希值作为位数组中的下标，将所有k个对应的比特置为1。

比如，下图hash1(x)=1，那么在第2个格子将0变为1（数组是从0开始计数的），hash2(x)=6，那么将第5个格子置为1，hash3(x)=16，那么将第16个格子置位1，依次类推。如下图所示（只演示hash1~hash3）：

如何判断数据是否存在？

知道了如何向布隆过滤器中添加一个数据，那么新来一个数据，我们如何判断其是否存在于这个布隆过滤器中呢？

很简单，我们只需要将这个新的数据通过上面自定义的几个哈希函数，分别算出各个值，然后看其对应的地方是否都是1，如果存在一个不是1的情况，那么我们可以说，该新数据一定不存在于这个布隆过滤器中。

那么反过来说，如果通过哈希函数算出来的值，对应的地方都是1，那么我们能够肯定的得出：这个数据一定存在于这个布隆过滤器中吗？

答案是否定的，因为多个不同的数据通过hash函数算出来的结果是会有重复的，所以会存在某个位置是别的数据通过hash函数置为的1。即：“假阳性”（false positive）如下图所示：