CuckooFilter详解
对于海量数据处理业务，我们通常需要一个索引数据结构，用来帮助查询，快速判断数据记录是否存在，这种数据结构通常又叫过滤器(filter)。考虑这样一个场景，上网的时候需要在浏览器上输入URL，这时浏览器需要去判断这是否一个恶意的网站，它将对本地缓存的成千上万的URL索引进行过滤，如果不存在，就放行，如果（可能）存在，则向远程服务端发起验证请求，并回馈客户端给出警告。
BloomFilter的缺陷
时下一个非常流行的哈希索引结构就是bloom filter，它类似于bitmap这样的hashset，所以空间利用率很高。其独特的地方在于它使用多个哈希函数来避免哈希碰撞，如图所示（来源wikipedia），bit数组初始化为全0，插入x时，x被3个哈希函数分别映射到3个不同的bit位上并置1，查询x时，只有被这3个函数映射到的bit位全部是1才能说明x可能存在，但凡至少出现一个0表示x肯定不存在。
但是，bloom filter的这种位图模式带来两个问题：一个是误报（false positives），在查询时能提供“一定不存在”，但只能提供“可能存在”，因为存在其它元素被映射到部分相同bit位上，导致该位置1，那么一个不存在的元素可能会被误报成存在；另一个是漏报（false nagatives），同样道理，如果删除了某个元素，导致该映射bit位被置0，那么本来存在的元素会被漏报成不存在。由于后者问题严重得多，所以bloom filter必须确保“definitely no”从而容忍“probably yes”，不允许元素的删除。
关于元素删除的问题，一个改良方案是对bloom filter引入计数（Counting Bloom filters），但这样一来，原来每个bit空间就要扩张成一个计数值，空间效率上又降低了。
Cuckoo Filter
为了解决这一问题，本文引入了一种新的哈希算法 —— cuckoo filter，它既可以确保该元素存在的必然性，又可以在不违背此前提下删除任意元素，仅仅比bitmap牺牲了微量空间效率。
Cuckoo Hash Tables
我们先来看看cuckoo hashing有什么特点，它的哈希函数是成对的（具体的实现可以根据需求设计），每一个元素都是两个，分别映射到两个位置，一个是记录的位置，另一个是备用位置。这个备用位置是处理碰撞时用的，这就要说到cuckoo这个名词的典故了，中文名叫布谷鸟，这种鸟有一种即狡猾又贪婪的习性，它不肯自己筑巢，而是把蛋下到别的鸟巢里，而且它的幼鸟又会比别的鸟早出生，布谷幼鸟天生有一种残忍的动作，幼鸟会拼命把未出生的其它鸟蛋挤出窝巢，今后以便独享“养父母”的食物。借助生物学上这一典故，cuckoo hashing处理碰撞的方法，就是把原来占用位置的这个元素踢走，不过被踢出去的元素还要比鸟蛋幸运，因为它还有一个备用位置可以安置，如果备用位置上还有人，再把它踢走，如此往复。直到被踢的次数达到一个上限，才确认哈希表已满，并执行rehash操作。
我们不禁要问发生哈希碰撞之前的空间利用率是多少呢？不幸地告诉你，一维数组的哈希表上跟其它哈希函数没什么区别，也就50%而已。但如果是二维的呢？
一个改进的哈希表如下图所示，每个桶（bucket）有4路槽位（slot）。当哈希函数映射到同一个bucket中，在其它三路slot未被填满之前，是不会有元素被踢的，这大大缓冲了碰撞的几率。笔者自己的简单实现上测过，采用二维哈希表（4路slot）大约80%的占用率（CMU论文数据据说达到90%以上，应该是扩大了slot关联数目所致）。
如上图所示，(a) 表示插入元素x之前已经存在的元素a, b, c。通过计算x的两个可用位置分别被a, b占用了，随机选择一个位置，也就是元素a存放的位置。然后元素a被迁移到它的备用位置，也就是元素c现在的位置。类似的c再做迁移。(c) 表示Cuckoo Hash的一种实现，每个bucket有四个slot。对于 (a) 的情形，则直接把x插入到元素a或b所在的bucket的空的slot里面即可。
Cuckoo Filter是Cuckoo Hash的一种更节省空间的变体，它在bucket中存放的不是元素本身，而是 fingerprint(x) 值，也是类似于一种哈希值。
Cuckoo Filter算法
Cuckoo Hash Table的基本单元叫做entry，每个entry存储一个fingerprint。Hash Table由多个bucket组成，每个bucket有多个entry。
插入
假设对于x的两个可用位置为i1, i2。当出现x需要迁移的时候，我们怎么得到它的另一个位置呢？因为bucket里面存放的是f = fingerprint值，所以i1，i2不能简单的通过两个哈希函数计算得到。这里使用异或运算达到i1，i2可以互相转化的目的。具体算法如下：
另外在我们为元素再分配地址（下面简称reallocate）的时候，如果一直找不到空闲的位置（比如x, y 的两个可用位置i1, i2完全相同），或者可以找到但是需要的时间出于性能方面的考虑不能忍受，这个时候就需要我们做一个限制，比如设置一个最大的reallocate的次数。
查找
查找很简单，但是需要注意的是存在误判的。
删除
删除也是删除的元素fingerprint值，存在误删的情况。
总结
Cuckoo Filter的优点是不言而喻的：
- 支持动态的插入、删除操作
- 整个数据结构接近满的时候，Cuckoo Filter具有更佳的查找性能（95%的空间利用率）
- 容易实现
- False Positive Rate比Bloom Filter更小，并且具有更高的空间利用率
同其他的filter比较：
但Cuckoo Filter还是有一些缺点：
- 由于进行XOR运算，使得Filter的个数必须为2的整数次幂
- 储存fingerprint在filter内当做特征值，虽然有一定好处，但是也存在碰撞机会而造成false positive