cuckoo hash 基本思想

基本思想:

cuckoo hash是一种解决hash冲突的方法,其目的是使用简单的hash函数来提高hash table的利用率,同时保证O(1)的查询时间
基本思想是使用2个hash函数来处理碰撞,从而每个key都对应到2个位置。

插入操作如下:

  • 对key值hash,生成两个hash key值,hashk1和 hashk2, 如果对应的两个位置上有一个为空,那么直接把key插入即可。
  • 否则,任选一个位置,把key值插入,把已经在那个位置的key值踢出来。
  • 被踢出来的key值,需要重新插入,直到没有key被踢出为止。

查找思路与一般hash一致。

cuckoo hash的扩展:

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

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

slot way Num1248
collision Factors装载率只能到53%,冲突率22%9%3.6%1.1%

注:上表中的同样条件是指cuckoo hash中特有的,在hash collision 时的搜索路径的次数一定时。从表中我们可以看到,在使用cityhash, 1 slot way 时,hash collision 的概率是很高的。

参考链接

Was this helpful?

0 / 0

发表回复 0