Cuckoo Hash——Hash冲突的解决办法

参考文献:

  1、Cuckoo Filter hash算法

  2、cuckoo hash

用途:

  Cuckoo Hash(布谷鸟散列)。问了解决哈希冲突的问题而提出,利用较少的计算换取较大的空间。占用空间少,查询速度快。经常应用于Bloom Filter和内存管理中。之所以起这个名字是因为布谷鸟生性贪婪,不自己筑巢,而是在别的鸟巢里面鸟蛋孵化,先成长的幼鸟会将别的鸟蛋挤出,这样独享“母爱”,类似于哈希冲突处理过程。

算法描述

  使用hashA、hashB计算对应的key位置:

    1、两个位置均为空,则任选一个插入;

    2、两个位置中一个为空,则插入到空的那个位置

    3、两个位置均不为空,则踢出一个位置后插入,被踢出的<key,value>对调用该算法,再执行该算法找其另一个位置,循环直到插入成功。

  如果被踢出的次数达到一定的阈值,则认为hash表已满,并进行重新哈希rehash

优化(减少哈希碰撞):

  1、将一维改成多维,使用桶(bucket)的4路槽位(slot);

  2、一个key对应多个value;

  3、增加哈希函数,从两个增加到多个;

  4、增加哈希表,类似于第一种;

原文地址:https://www.cnblogs.com/xiangyangzhu/p/5452066.html