Bloom filter 布隆过滤器
布隆过滤器是一种数据结构，旨在以内存高效的方式快速确定元素是否存在于集合中，具有运行快速，内存占用小的特点。
优点是空间效率和查询时间，缺点是有一定的误识别率和删除困难
基本概念
如果想判断一个元素是不是在一个集合里，一般是将集合中的所有元素保存起来。链表、数等数据结构都是这种思路，但是随着数据量越来越大，时间检索也越来越慢。
而布隆过滤器的原理是：当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是1就大概知道集合中有没有它。如果任意一个0，则一定不存在，如果都是1，则很可能存在。
image.png
优点：
1、相比于其他数据结构，布隆过滤器在空间和时间方面都有很大优势(O(k))。
2、不需要存储元素本身
缺点：
1、误算率，随着数据量增加，误算率也会增加
2、不能删除元素(计数Bloom过滤器变体解决)
3、计数回绕
Cuckoo filter 布谷鸟过滤器
布隆过滤器的替代品，具有从集合中删除元素的额外支持
名字起源于Cuckoo(布谷鸟)的行为，在孵化时，将其他的蛋或幼鸟从巢中推出。类似地Cuckoo hash，将新指纹会将较旧的指纹推入到其他位置。
image.png
布谷哈希：一个基本的布谷哈希表由一个桶数组组成，其中每个桶位置由哈希函数h1(x)和h2(x)确定。如上图将X插入到包含8个桶的哈希表，x可以放到bucket(桶)2或 bucket(桶)6中，如果这两个桶有一个是空，则会插到空闲桶，插入完成。如果没有空间像上图a中，那么将会候选一个bucket(桶)。假如是bucket(桶)6，则当前a将会重新插入到自己的备用位置bucket(桶)4，此时这个桶有c，将会重定位c从bucket(桶)4踢到bucket(桶)1。最终效果如上图b插入x之后。
重新定位替代位置
由于布谷鸟过滤器存储的不是键，而是指纹。所以为了能够根据当前位置和指纹计算出备用位置，设计了特殊的hash函数
h1(x) = hash(x)
h2(x) = h1(x) ^ hash(x’s fingerprint)
根据异或运算，h1(x)也可以从这个公式中从h2(x) 和指纹中计算出来。所以无论是计算 h1(x)或h2(x)都可以通过当前桶索引和存储的指纹计算出来(利用对偶性)，而不必检索原始项x。
当然，为了不会出现自己踢自己的问题出现(h1(x)不等于h2(x))，需要确保hash(x’s fingerprint)不等于0
空间利用率
由于没有改善的布谷鸟哈希的平均利用率并不高，没有利用价值。改善方法包括增加hash函数和每个桶有多个位置。
image.png
如图，两个哈希函数，每个桶拥有4个条目数。
当桶拥有的条目数是4可以填充到95%的占有率
当桶拥有的条目数是8可以填充到98%的占有率
所以，更好的是两种方式结合
插入、查找和删除
f = fingerprint(x);
i1 = hash(x);
i2 = i1 ^ hash(f);
插入：插入包含一个最大挤兑次数
首先尝试加入第一个位置，如果失败则尝试加入第二个位置。如果还是失败，则随机挤兑一个。并在挤兑次数限制下进行循环挤兑。
对于相同的指纹，kb+1次便会失败插入不进去直到最大挤兑次数。k是hash次数，b是桶上的条目数。
例如两个hash函数，8个桶上的条目数则第17次会插入不进去
查找：根据布谷鸟哈希查找桶中(i1和i2)是否包含x的指纹，如果包含则返回true
删除：删除和查找一样，查到后删除并返回true
参考文档：
cuckoo-conext2014
CuckooHashing
总结：
两种过滤器的哈希算法
布隆过滤器和布谷鸟过滤器都是快速判断集合中是否存在某个元素
布谷鸟过滤器是布隆过滤器的替代品
在redis的应用，可以解决缓存穿透问题
网友评论