Motivation & Intuition

为什么引入Cuckoo Hashing？

常见的hashing处理冲突方法一般包括两种：Separate Chaining和Open Addressing（Linear Probing）。Separate Chaining是将冲突的元素组织成一个链表（其实组织成一个二叉搜索树也是完全没问题的，甚至跳表也行），Open Addressing将冲突的元素还是放在哈希表slot中，使用线性探测等方法进行处理。

那么，这两种方法，都有啥优缺点呢？

Separate Chaining : 实现简单，但是对cache不友好，cache miss rate较高。

Open Addressing : 实现相对复杂一点点，对cache很友好，但是对load factor要求苛刻：load factor稍高性能就急剧下降。

这两种方式下，查找某个元素的最坏时间都是O(n)。

你说，OK，OK，我知道，这些都是常识。那么，是否可以做到查找最坏是O(1)呢？

一种思路是元素只可能被安置到有限的常数(记为K)个位置，插入时，如果发生冲突，由于每个元素可以存放的位置有K个，因此可以对表部分元素进行重排，产生一个空缺的位置。

Cuckoo Hashing就是这样的方式。当K=2时，Cuckoo Hashing在load factor为50%左右的情况下表现较佳。如果K=4，那么甚至可以在97%的load factor下良好工作。

Cuckoo Hashing

一般的Hashing只包括一个Hash Tables，但是Cuckoo Hashing由两张甚至多张表构成。每张表对应一个哈希函数。本文讨论两张哈希表（记为table1和table2）、两个哈希函数（记为hf1和hf2）这种常见情形。

Insert

首先通过hf1计算出一个slot index，然后查看table1中该slot是否vacant，如果是，则插入；否则通过hf2计算出一个slot index，通过查看table2中该slot是否vacant，如果是，则插入，否则执行rearrange操作。

rearrange操作的过程：随机选出一张表，将slot index对应的那个元素踢出(evict)，把我们待插入的元素插到那个位置。那被踢出来的元素呢？尝试插入到另外一张表对应的slot处，这时候可能又踢出一个元素，接下去就是递归的执行这个过程，直到所有元素都安置妥当。

举个例子吧，假如某个时刻，两个哈希表的内容如下：

假设我们待插入的元素为77。

slot index1 = hf1(77) = 1

Table1中的index为1的slot已经被78占了。那么看Table2：

slot index2 = hf2(77) = 3

Table2中的index为3的slot已经被33占了。因此执行rearrange。

执行rearrange动作，选择Table2，将slot index = 3的元素33踢出，插入77。然后被踢出的元素33，计算它在Table1中的index为slot index1 = hf2(33) = 2，因此将95踢出，插入33。被踢出的元素95在Table2中的slot index为2，该slot为vacant，没人使用，因此将95插入。完毕。现在的Tables中元素为：

值得注意的是，rearrange可能失败（表满了;或者发生“死循环”），此时需要进行rehash，因此代码里需要有一定的判断。当K=2时，只要load factor低于50%，需要rehash的概率很小很小。

在某些假设下，插入操作的摊还期望复杂度为常数时间。

Find

要检查的slot一共两个，index分别为hf1(key)和hf2(key)，因此只要查看一下Table1中的hf1(key)以及Table2中的hf2(key)这两个slot即可。时间复杂度为O(1)。

Del

同Find，要检查的slot也就两个，复杂度为O(1)。

实现

实现了Bucketized Cuckoo Hashmap，有需要的可以参考这里

其他

1，我们注意到，Cuckoo Hashing的精髓是使用两个不同的哈希函数，而不是两张表。两张表的存在，仅仅是为了分析上的方便。

当需要rehash而load factor又没达到100%时，我们其实不需要扩容哈希表，只需要更换哈希函数。

2，为嘛叫做Cuckoo Hashing？Cuckoo，即杜鹃鸟（布谷鸟），这种鸟有一种尿性：孵卵寄生。把蛋产到别的鸟窝里，让别人帮它孵化。这还不算，还要把人家寄主的一些卵给移走（不然容易引起怀疑嘛，毕竟鸟窝里突然多出几枚蛋。至于移走多少，就得看杜鹃鸟数学合不合格了）！等卵孵化完成，幼雏会将鸟窝里寄主的卵和其他幼雏推出鸟窝。真是牛逼闪闪了。

参考文献

http://resources.mpi-inf.mpg.de/departments/d1/teaching/ws14/AlgoDat/materials/cuckoo.pdf

Cuckoo Hashing原始论文

https://www.eecs.harvard.edu/~michaelm/postscripts/esa2009.pdf

这篇文章介绍了一些关于Cuckoo Hashing的Open Questions

http://web.stanford.edu/class/cs166/lectures/13/Slides13.pdf

这个slides偏重对Cuckoo Hashing理论上的分析，注意其中对于插入操作的处理和本文介绍的不同。

http://excess-project.eu/publications/published/CuckooHashing_ICDCS.pdf

碉堡了，Lock Free Cuckoo Hashing。