布隆过滤器的原理

转载：https://www.toutiao.com/a6836181257961865740/

背景：

布隆过滤器是一种标记大量数据是否存在的数据结构，能够节省大量的空间并且提高效率。

布隆过滤器判断存在的数据，可能并不存在；其判断不存在的数据，就一定不存在。这是为什么？又为什么不提供删除操作？

布隆过滤器

布隆过滤器是一种基于概率的数据结构，主要用来判断某个元素是否在集合内，它具有运行速度快（时间效率），占用内存小的优点（空间效率），但是有一定的误识别率和删除困难的问题。它只能告诉你某个元素一定不在集合内或可能在集合内。

在计算机科学中有一种思想：空间换时间，时间换空间。一般两者是不可兼得，而布隆过滤器运行效率和空间大小都兼得，它是怎么做到的呢？

在布隆过滤器中引用了一个误判率的概念，即它可能会把不属于这个集合的元素认为可能属于这个集合，但是不会把属于这个集合的认为不属于这个集合，布隆过滤器的特点如下：

一个非常大的二进制位数组 （数组里只有0和1）

若干个哈希函数

空间效率和查询效率高

不存在漏报（False Negative）：某个元素在某个集合中，肯定能报出来。

可能存在误报（False Positive）：某个元素不在某个集合中，可能也被爆出来。

不提供删除方法，代码维护困难。

位数组初始化都为0，它不存元素的具体值，当元素经过哈希函数哈希后的值（也就是数组下标）对应的数组位置值改为1。

实际布隆过滤器存储数据和查询数据的原理图如下：

可能很多读者看完上面的特点和原理图，还是看不懂，别急下面通过图解一步一步的讲解布隆过滤器，总而言之一句简单的话概括就是布隆过滤器是一个很大二进制的位数组，数组里面只存0和1。

初始化的布隆过滤器的结构图如下：

以上只是画了布隆过滤器的很小很小的一部分，实际布隆过滤器是非常大的数组（这里的大是指它的长度大，并不是指它所占的内存空间大）。

那么一个数据是怎么存进布隆过滤器的呢？

当一个数据进行存入布隆过滤器的时候，会经过若干个哈希函数进行哈希（若是对哈希函数还不懂的请参考这一片[]），得到对应的哈希值作为数组的下标，然后将初始化的位数组对应的下标的值修改为1，结果图如下：

数据x经过哈希函数的运算后，下标为2，10，因此把这2个下标的值设置为1。

当再次进行存入第二个值的时候，修改后的结果的原理图如下：

数据y经过哈希函数的运算后，下标为13，23，因此把这2个下标的值设置为1。

所以每次存入一个数据，就会哈希函数的计算，计算的结果就会作为下标，在布隆过滤器中有多少个哈希函数就会计算出多少个下标，布隆过滤器插入的流程如下：

将要添加的元素给m个哈希函数

得到对应于位数组上的m个位置

将这m个位置设为1

那么为什么会有误判率呢？

假设在我们多次存入值后，在布隆过滤器中存在x、y、z这三个值，布隆过滤器的存储结构图如下所示：

数据z经过哈希函数的运算后，下标为10，13，因此把这2个下标的值设置为1。

当我们要查询的时候，比如查询a这个数，实际中a这个数是不存在布隆过滤器中的，经过2个哈希函数计算后得到a的哈希值分别为2和13，结构原理图如下：

数据a经过哈希函数的运算后，下标为2，13

经过查询后，发现2和13位置所存储的值都为1，但是2和13的下标分别是x和z经过计算后的下标位置的修改，该布隆过滤器中实际不存在a，那么布隆过滤器就会误判该值可能存在，因为布隆过滤器不存元素值，所以存在误判率。

那么具体布隆过布隆过滤的判断的准确率和一下两个因素有关：

布隆过滤器大小：越大，误判率就越小，所以说布隆过滤器一般长度都是非常大的。

哈希函数的个数：哈希函数的个数越多，那么误判率就越小。

那么为什么不能删除元素呢？

原因很简单，因为删除元素后，将对应元素的下标设置为零，可能别的元素的下标也引用改下标，这样别的元素的判断就会收到影响，原理图如下：

当你删除z元素之后，将对应的下标10和13设置为0，这样导致x和y元素的下标受到影响，导致数据的判断不准确，所以直接不提供删除元素的api。

以上说的都是布隆过滤器的原理，只有理解了原理，在实际的运用才能如鱼得水，下面就来实操代码，手写一个简单的布隆过滤器。