原书出处
大数据日知录_架构与算法
03 大数据常用的算法与数据结构
传统哈希方法只使用一个哈希函数,为了较好地解决哈希冲突问题,Cuckoo哈希同时使用两个不同的哈希函数H 1 (x )和H 2 (x )。当插入数据x 时,同时计算H 1 (x )和H 2 (x ),如果对应的哈希空间中任意一个桶(Bucket)为空,则可以将x 插入相应位置;如果两者都不空,则选择一个桶,将已经占据这个位置的值y 踢出去,由x 来占据这个位置。对于y 来说,重复上述过程,即重新计算其对应的两个哈希函数H 1 (y )和H 2 (y ),如果有空桶,则将y 插入新的位置,如果没有空桶,则踢出已经占据位置的z ,之后反复这个过程,直到所有数值都找到空桶安置。对于Cuckoo哈希来说,上述过程可能导致无限循环,一般做法是设定最大替换次数,当达到最大替换次数时,要么增加哈希空间中桶的数量,要么重新选择合适的哈希函数来替换之前的哈希函数。下面是Cuckoo哈希算法的伪码描述,与上面所述不同的是:分别对应两个哈希函数,其采用了两个存放哈希值的数组T 1 和T 2 。
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html
EPUB SHA-256:e45b74c4bdd8959aef24f2a5183280eb73ec5f173108f8679a4bbf44bbd5b34d