返回主题:存储常用数据结构

知识卡片

普通读书笔记卡 · 1770.e

Cuckoo驱逐冲突

理解等级:中级

Cuckoo Hashing 为元素准备多个候选位置,冲突时把旧元素“踢出”并递归安置。它让查询保持常数时间,但插入可能触发连锁迁移,空间利用率和重建策略决定稳定性。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 大数据常用的算法与数据结构 · 查看原书依据

      传统哈希方法只使用一个哈希函数,为了较好地解决哈希冲突问题,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 。

    参考来源

    - 位置:《大数据日知录:架构与算法》第3章《大数据常用的算法与数据结构》(来源项目:book-sources;源文件:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html) - 结论依据:原文以“Cuckoo哈希同时使用两个不同的哈希函数”所在段落解释具体机制;本卡保留其条件,另将实现限制、勘误和教学推导在正文中明确区分。 - 原始内容:传统哈希方法只使用一个哈希函数,为了较好地解决哈希冲突问题,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 。