但是在讲布谷鸟过滤器之前，得简单的铺垫一下 Cuckoo hashing，也就是布谷鸟 hash 的知识。
因为这个词是论文的关键词，在文中出现了 52 次之多。
Cuckoo hashing，最早出现在这篇 2001 年的论文之中：
https://www.cs.tau.ac.il/~shanir/advanced-seminar-data-structures-2009/bib/pagh01cuckoo.pdf
主要看论文的这个地方：
它的工作原理，总结起来是这样的：
它有两个 hash 表，记为 T1，T2。
两个 hash 函数，记为 h1，h2。
当一个不存在的元素插入的时候，会先根据 h1 计算出其在 T1 表的位置，如果该位置为空则可以放进去。
如果该位置不为空，则根据 h2 计算出其在 T2 表的位置，如果该位置为空则可以放进去。
如果该位置不为空，就把当前位置上的元素踢出去，然后把当前元素放进去就行了。
也可以随机踢出两个位置中的一个，总之会有一个元素被踢出去。
被踢出去的元素怎么办呢？
没事啊，它也有自己的另外一个位置。
论文中的伪代码是这样的：
看不懂没关系，我们画个示意图：
上面的图说的是这样的一个事儿：
我想要插入元素 x，经过两个 hash 函数计算后，它的两个位置分别为 T1 表的 2 号位置和 T2 表的 1 号位置。
两个位置都被占了，那就随机把 T1 表 2 号位置上的 y 踢出去吧。
而 y 的另一个位置被 z 元素占领了。
于是 y 毫不留情把 z 也踢了出去。
z 发现自己的备用位置还空着（虽然这个备用位置也是元素 v 的备用位置），赶紧就位。
所以，当 x 插入之后，图就变成了这样：
上面这个图其实来源就是论文里面：
这种类似于套娃的解决方式看是可行，但是总是有出现循环踢出导致放不进 x 的问题。
比如上图中的(b)。
当遇到这种情况时候，说明布谷鸟 hash 已经到了极限情况，应该进行扩容，或者 hash 函数的优化。
所以，你再次去看伪代码的时候，你会明白里面的 MaxLoop 的含义是什么了。
这个 MaxLoop 的含义就是为了避免相互踢出的这个过程执行次数太多，设置的一个阈值。
其实我理解，布谷鸟 hash 是一种解决 hash 冲突的骚操作。
如果你想上手玩一下，可以访问这个网站：
http://www.lkozma.net/cuckoo_hashing_visualization/
当踢来踢去了 16 （MaxLoop）次还没插入完成后，它会告诉你，需要 rehash 并对数组扩容了：
布谷鸟 hash 就是这么一回事。
接着，我们看布谷鸟过滤器。
