Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

Introduction To Cuckoo Hashing

Motivation & Intuition

为什么引入Cuckoo Hashing

常见的hashing处理冲突方法一般包括两种:Separate ChainingOpen AddressingLinear 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 Hashingload factor50%左右的情况下表现较佳。如果K=4,那么甚至可以在97%load factor下良好工作。

Cuckoo Hashing

一般的Hashing只包括一个Hash Tables,但是Cuckoo Hashing由两张甚至多张表构成。每张表对应一个哈希函数。本文讨论两张哈希表(记为table1table2)、两个哈希函数(记为hf1hf2)这种常见情形。

Insert

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

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

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

table1

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

slot index1 = hf1(77) = 1

Table1中的index1slot已经被78占了。那么看Table2

slot index2 = hf2(77) = 3

Table2中的index3slot已经被33占了。因此执行rearrange

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

table2

值得注意的是,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的精髓是使用两个不同的哈希函数,而不是两张表。两张表的存在,仅仅是为了分析上的方便。

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

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

参考文献

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 HashingOpen 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