首页 > 代码库 > 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 Num | 1 | 2 | 4 | 8 |
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算法分析