首页 > 代码库 > Cuckoo hash算法分析

Cuckoo hash算法分析

一 基本思想:

cuckoo hash是一种解决hash冲突的方法,其目的是使用简单的hash 函数来提高hash table的利用率,同时保证O(1)的查询时间

基本思想是使用2个hash函数来处理碰撞,从而每个key都对应到2个位置。

插入操作如下:

1. 对key值hash,生成两个hash key值,hashk1和 hashk2, 如果对应的两个位置上有一个为空,那么直接把key插入即可。

2. 否则,任选一个位置,把key值插入,把已经在那个位置的key值踢出来。

3. 被踢出来的key值,需要重新插入,直到没有key被踢出为止。

 

查找思路与一般hash一致。

 cuckoo hash的扩展:

1、减小hash碰撞

一个key对应的hash table位置处存储多个value(从slot way到 多个 slot way),从而以增加查找与插入时间为代价减小hash碰撞。

做了个实验,比较不同slot way 下 同样装载率(75%)下的碰撞率(hash 函数使用的是cityhash):

slot way Num1248
collision Factors同样条件最大装载率为30%9%3.6%1.1%

 表1

注:表1中的”同样条件“是指cuckoo hash中特有的,在hash collision 时的搜索路径的次数一定时。

   从图中我们可以看到,在使用cityhash, 1 slot way 时,hash collision 的概率是很高的。

 

参考链接如下:

http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf

http://www.it-c.dk/people/pagh/papers/cuckoo-jour.pdf

http://en.wikipedia.org/wiki/Cuckoo_hashing

http://hi.baidu.com/algorithms/blog/item/eb89b582add48f95f703a61e.html

http://blog.csdn.net/suwei19870312/article/details/7442786

Cuckoo hash算法分析