布隆过滤器和布谷鸟过滤器详解

今天和大家分享下布隆过滤器和布谷鸟过滤器

一.布隆过滤器

1.简单介绍

布隆过滤器是用于检索一个元素是否在一个集合中的算法，是一种用空间换时间的查询算法。

2.实现原理

布隆过滤器的存储结构是一个bitmap结构，初始值都是0，如下图所示：

当需要存储一个数据的时候，会通过多次(这里假设为3次)hash函数运算之后，计算出3个hash值，然后将计算出的这3个hash值当做坐标，将数组对应的坐标数据由0改成1，以此来标记这个数据已经存储在数组中了。如下图所示：

等到需要查询数据是否在数组中时，就通过hash计算出对应的坐标，判断是否全都为1，如果都为1数据就可能存在，如果有一个为0，则数据一定不存在。

• 为什么这里说可能存在能，因为可能会出现hash碰撞的情况，不同的数据经过hash函数运算之后，计算出来的hash坐标却相同，导致数据本来不存在数组中，但是这里却判断存在，因此布隆过滤器会出现误判的情况，但是概率会很低，误判的概率和设置的hash运算次数是成反比的。
  如下图所示：
  
  Data和Data2的hash值一样，但是Data数据存在，Data2不存在，在判断Data2的时候，布隆过滤器就会判断Data2也存在，由此产生误判。

这里有个很有意思的网站，大家可以自己动手去看下数据存储的具体过程：https://www.jasondavies.com/bloomfilter/网站内容如下:

总的来说，布隆过滤器的判断：存在->可能存在，不存在->一定不存在。

• 根据上述特性，布隆过滤器在很多场景下，可以帮我们判断大部分的判断请求。因此较多用于高并发的场景下使用，比如处理缓存击穿、用户视频推荐等场景。

3. 布隆过滤器的缺点

• 误判：
  上文已经说明一点了，就是布隆过滤器会产生误判，在此就不过多赘述了。
• 当数组过大时，查询效率不高：
  因为布隆过滤器的判断方式是根据多次hash值判断的，当数组过大，那么hash值的跨度可能就越大，跨度大就是不连续，那么CPU的缓存命中率就会变低，就会影响查询效率。
• 布隆过滤器不能删除元素：
  因为不同的数据可能会计算出相同的hash值，因此我们如果要删除某个元素，可能也会影响其他的元素的判断。在这个限制条件下，当数据量大的时候，就会导致很多的垃圾数据。并且数据量越大，误判率也就会越高。

二.布谷鸟过滤器

1.简单介绍

布谷鸟过滤器可以说是一个增强版的布隆过滤器，可以删除元素，查询效率更高，空间利用率更高。

2.实现原理

布谷鸟过滤器不同于布隆过滤器主要有两点改动：

• hash算法：
  在布谷鸟过滤器中，数组中存储的是每个元素的"指纹信息"，也就是hash运算之后的几个bit位。查询数据的时候，就是看看对应的位置上有没有对应的“指纹”信息，删除数据的时候，也只是抹掉该位置上的“指纹”而已。
• 由于指纹是对元素进行 hash 计算得出的，那么必然会出现 hash 碰撞的问题，也就是“指纹”相同的情况，也就是会出现误判的情况，所以这点和布隆过滤器一样。
  布谷鸟过滤器的hash算法是基于布谷鸟哈希算法做了改进，计算公式如下：

fp = fingerprint(x)
h1 = hash(x)
h2 = h1 ^ hash(fp)  // 异或

• 在上列公式可以看出，h2的位置是根据h1的位置计算出来的，也就是说我们知道了其中一个位置，就可以直接获取到另外一个位置，不需要再做全量的hash运算。因为使用的异或运算，所以这两个位置具有对偶性。这也是提高查询效率的一个点。
  只要保证 hash(fp) !=0，那么就可以确保 h2!=h1，也就可以确保不会出现自己踢自己的死循环问题了。
• 这里还有个注意点：就是hash运算的时候，并没有对值进行长度取模运算，那么他是如何保证计算出来hash坐标，一定是在数组长度范围内呢？这就说到布谷鸟过滤器的一个限制条件了，那就是强制数组的长度必须是 2 的指数倍
  这个限制带来的好处就是，进行异或运算时，可以保证计算出来的下标一定是落在数组中的。

布谷鸟过滤器对布隆过滤器的另一个优化点就是存储结构：

• 布谷鸟过滤器的存储结构是每个坐标下的空位是多个，不同于布隆过滤器的一个空位。如下图所示：
  布谷鸟过滤器会记录每个元素的两个hash位置，每个位置下都会有多个空位，空位内存储的就是元素的“指纹信息”。
• 布谷鸟过滤器添加元素的流程是这样的：
  布谷鸟过滤器会先计算出元素对应的指纹信息，然后对元素进行hash运算，计算出元素的第一个存储坐标，该坐标下存在四个空位，如果四个空位中有空闲的，就将该元素的指纹信息存进去；如果没有空位，就会根据指纹和第一个hash坐标进行异或运算，计算出第二个坐标，如果第二个坐标下有空位，就将该元素的指纹信息存进去；如果还没有空位，那么该元素就会随机将一个空位中的指纹信息挤出，然后自己存进去，被挤出的指纹信息会计算出自己的第二个坐标，然后判断是否有空位，重复上述操作，直到达到一个阀值，布谷鸟过滤器返回false或进行扩容处理。

流程如下所示：

数据Data想要存储到布谷鸟过滤器中，首先会计算出h1和h2两个存储坐标，结果发现两个坐标的空位都已经“满员”了，此时会随机挤掉一个元素的指纹信息，假设挤掉了h1坐标的指纹3，然后指纹3会找自己的第二个坐标，然后判断是否有空位，有空位就存到第二个坐标下，如下图：

扩容：如果数组过小，会发生循环挤兑的情况，就可以设置最大挤兑次数，如果超过该次数，进行扩容，重新计算每个指纹的位置。

当 hash 函数固定为 2 个的时候，如果一个下标只能放一个元素，那么空间利用率是 50%。如果为 2，4，8 个元素的时候，空间利用率分别是 84%，95%，98%，可以发现空间利用率飙升。

3.布隆过滤器的缺点

• 删除不完美，存在误删的概率。删除的时候知识删除了一份指纹副本，并不能确定此指纹副本是要删除的key的指纹。同时这个问题也导致了假阳性的情况。
• 插入复杂度比较高。随着插入元素的增多，复杂度会越来越高，因为存在桶满，踢出的操作，所以需要重新计算，但综合来讲复杂度还是常数级别。
• 存储空间的大小必须为2的指数的限制让空间效率打了折扣。
• 同一个元素最多插入kb次，（k指哈希函数的个数，b指的是坐标下能装指纹的个数也可以说是坐标下桶的尺寸大小）如果布谷鸟过滤器支持删除，则必须存储同一项的多个副本。 插入同一项kb+1次将导致插入失败。 这类似于计数布隆过滤器，其中重复插入会导致计数器溢出。