🧐Cuckoo Filter：Better Than Bloom
Last updated
Last updated
布隆过滤器有缺点，比如不支持删除操作、查询效率弱，因为多个随机哈希函数探测的是bit数组中多个不同的点，所以会导致低CPU缓存命中率
乐，我就是比你弔：
Cukoo解决了这个问题：用更低的空间开销解决了布隆过滤器不能删除元素的问题
supports adding and removing items dynamically （动态的添加和删除元素）
higher lookup performance, even when close to full （更高的查找性能，即使在接近满的情况下）
easier to implement than alternatives such as the quotient filter （比起商过滤器它更容易实现）
less space if the target false positive rate is less than 3% （如果要求误判率低于3%，它比布隆过滤器有更低的空间开销）
最原始的布谷鸟哈希方法是使用两个哈希函数对一个key进行哈希，得到桶中的两个位置，此时
如果两个位置都为为空则将key随机存入其中一个位置
如果只有一个位置为空则存入为空的位置
如果都不为空，则随机踢出一个元素，踢出的元素再重新计算哈希找到相应的位置
当然假如存在绝对的空间不足，那老是踢出也不是办法，所以一般会设置一个踢出阈值，如果在某次插入行为过程中连续踢出超过阈值，则进行扩容。
换言之：
它有两个 hash 表，记为 T1，T2。
两个 hash 函数，记为 h1，h2。
当一个不存在的元素插入的时候，会先根据 h1 计算出其在 T1 表的位置，如果该位置为空则可以放进去。
如果该位置不为空，则根据 h2 计算出其在 T2 表的位置，如果该位置为空则可以放进去。
如果该位置不为空，就把当前位置上的元素踢出去，然后把当前元素放进去就行了。
也可以随机踢出两个位置中的一个，总之会有一个元素被踢出去。
被踢出去的元素怎么办呢？
这种类似于套娃的解决方式看是可行，但是总是有出现循环踢出导致放不进 x 的问题。
比如上图中的(b)
当遇到这种情况时候，说明布谷鸟 hash 已经到了极限情况，应该进行扩容，或者 hash 函数的优化。所以，你再次去看伪代码的时候，你会明白里面的 MaxLoop 的含义是什么了。
这个 MaxLoop 的含义就是为了避免相互踢出的这个过程执行次数太多，设置的一个阈值。
（a）(b)展示了一个基本的布谷鸟哈希表的插入操作，是由一个桶数组组成，每个插入项都有由散列函数h1(x)和h2(x)确定的两个候选桶，具体操作上文中已经描述。
而基本的布谷鸟过滤器也是由两个或者多个哈希函数构成，布谷鸟过滤器的布谷鸟哈希表的基本单位称为条目（entry）。 每个条目存储一个指纹（fingerprint）。
指纹指的是使用一个哈希函数生成的n位比特位，n的具体大小由所能接受的误判率来设置，论文中的例子使用的是**8 bits**的指纹大小。
查询数据的时候，就是看看对应的位置上有没有对应的“指纹”信息：
删除数据的时候，也只是抹掉该位置上的“指纹”而已：
由于是对元素进行 hash 计算，那么必然会出现“指纹”相同的情况，也就是会出现误判的情况。
没有存储原数据，所以牺牲了数据的准确性，但是只保存了几个 bit，因此提升了空间效率。
前面的(a)、(b)很简单，还是两个 hash 函数，但是没有用两个数组来存数据，就是基于一维数组的布谷鸟 hash ，核心还是踢来踢去，重点在于(c)，对数组进行了展开，从一维变成了二维：每一个下标，可以放 4 个元素了，空间利用率飙升！
_缺点_详见论文第六节or本文下面
插入是重点，与朴素的布谷鸟哈希不同。首先，我们回忆一下布谷鸟 hash，它存储的是插入元素的原始值，比如 x，x 会经过两个 hash 函数，如果我们记数组的长度为 L，那么就是这样的：
p1 = hash1(x) % L
p2 = hash2(x) % L
布谷鸟过滤器采取了两个并不独立的哈希函数:
先说指纹：具体的指纹是通过哈希函数取一定量的比特位:
f = fingerprint(x)
下面是哈希函数：
i1 = h1(x) = hash(x) 通过某个哈希函数计算出来
i2 = h2(x) = i1 ⊕ hash(f) 使用第一个索引和指纹的哈希做了一个异或操作
i1、i2即计算出来两个桶的索引。进行异或操作是因为异或操作的特性：同为0不同为1，且0和任何数异或是这个数的本身。异或运算确保了一个重要的性质：位置 i2 可以通过位置 i1 和 i1 中存储的“指纹”计算出来，即：在桶中迁走一个键，我们直接用当前桶的索引i和存储在桶中的指纹计算它的备用桶。
因为使用的异或运算，所以这两个位置具有对偶性。
只要保证 hash(x’s fingerprint) !=0，那么就可以确保 h2!=h1，也就可以确保，不会出现自己踢自己的死循环问题。
为什么不直接用索引1和指纹做异或操作：因为指纹一般只是key映射出来的少量bit位置，那么假如不进行哈希操作，当指纹的比特位与整个桶数组相比很小时，那么备用位置使用“i ⊕ 指纹”，将被放置到离桶i1很近的位置，比如使用八位的指纹大小，最多只能改变i1的低八位，所以也就是两个候选通的位置最多相差256，不利于均匀分配。
所以，对“指纹”进行哈希处理可确保被踢出去的元素，可以重新定位到哈希表中完全不同的存储桶中，从而减少哈希冲突并提高表利用率。
还有个问题：
它没有对数组的长度进行取模，那么它怎么保证计算出来的下标一定是落在数组中的呢？
这个就得说到布谷鸟过滤器的另外一个限制了：
其强制数组的长度必须是 2 的指数倍：二进制一定是这样的：10000000...（n个0）。
这个限制带来的好处就是，进行异或运算时，可以保证计算出来的下标一定是落在数组中的。
这个限制带来的坏处就是：
布谷鸟过滤器：我支持删除操作。
布隆过滤器：我不需要限制长度为 2 的指数倍。
布谷鸟过滤器：我查找性能比你高。
布隆过滤器：我不需要限制长度为 2 的指数倍。
布谷鸟过滤器：我空间利用率也高。
布隆过滤器：我不需要限制长度为 2 的指数倍。
布谷鸟过滤器：我烦死了，CNM！
给定一个项x，算法首先根据上述插入公式，计算x的指纹和两个候选桶。然后读取这两个桶：如果两个桶中的任何现有指纹匹配，则布谷鸟过滤器返回true，否则过滤器返回false。此时，只要不发生桶溢出，就可以确保没有假阴性
标准布隆过滤器不能删除，因此删除单个项需要重建整个过滤器，而计数布隆过滤器需要更多的空间。
布谷鸟过滤器就像计数布隆过滤器，可以通过从哈希表删除相应的指纹从而删除插入的项，其他具有类似删除过程的过滤器比布谷鸟过滤器更复杂。
具体删除的过程也很简单，检查给定项的两个候选桶；如果任何桶中的指纹匹配，则从该桶中删除匹配指纹的一份副本。
**删除不完美，存在误删的概率。**删除的时候只是删除了一份指纹副本，并不能确定此指纹副本是要删除的key的指纹。同时这个问题也导致了假阳性的情况。
**插入复杂度比较高。**随着插入元素的增多，复杂度会越来越高，因为存在桶满，踢出的操作，所以需要重新计算，但综合来讲复杂度还是常数级别。
存储空间的大小必须为2的指数的限制让空间效率打了折扣。
同一个元素最多插入kb次，（k指哈希函数的个数，b指的桶中能装指纹的个数也可以说是桶的尺寸大小（一个下标能放几个元素））如果布谷鸟过滤器支持删除，则必须存储同一项的多个副本。 插入同一项kb+1次将导致插入失败。 这类似于计数布隆过滤器，其中重复插入会导致计数器溢出。
比如 2 个 hash 函数，一个二维数组，它的每个下标最多可以插入 4 个元素。那么对于同一个元素，最多支持插入 8 次。
例如下面这种情况：
why 已经插入了 8 次了，如果再次插入一个 why，则会出现循环踢出的问题，直到最大循环次数，然后返回一个 false。
怎么避免这个问题呢
我们维护一个记录表，记录每个元素插入的次数就行了。
虽然逻辑简单，但是想想数据量大的情形，这个表的存储空间又怎么算呢？emmmmmm
桶的尺寸：
是指每个桶能放的指纹个数，保持布谷鸟过滤器的总大小（桶数组）不变，但改变桶的大小（上述例子使用的是大小为4）会导致两个后果：
(1) 较大的桶可以提高表的利用率(即b越大假阳性率越大) ，使用k=2个哈希函数时，当桶大小b=1（即直接映射哈希表）时，负载因子α为50%，但使用桶大小b=2、4或8时则分别会增加到84%、95%和98%。
(2) 较大的桶需要较长的指纹才能保持相同的假阳性率(即b越大f越大)。 使用较大的桶时，每次查找都会检查更多的条目，从而有更大的概率产生指纹冲突。
所以要基于以上寻找一个最合适的桶大小
