知识卡片

普通读书笔记卡 · 1292.g.1.b.1.h · 生成模型:未记录

开放定址依赖探测与删除规则

理解等级:中级

开放定址将元素放入桶数组的槽中;查找沿与插入一致的探测序列前进,遇到从未使用的空槽才可判定不存在。删除不能简单地把已使用槽改为从未使用,否则会截断后续元素的探测链;可使用删除标记或合适的回填策略。

线性探测可能产生聚集,二次探测需要参数和表容量满足覆盖要求;容量接近满时探测成本上升。书中探测次数公式是特定均匀散列模型下的期望界,不是所有实现的最坏界;最坏可扫描 O(b) 个槽。扩容需重新映射元素,并把一次性成本与摊销成本区分。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      开放定址的技术,这种技术直接将冲突元素存储在散列表A中。如图5-7所示。使用了开放定址技术,散列表减少了存储开销,例如在冲突的链表中使用指针指向元素。使用开放定址技术,我们将散列函数调整成为带两个参数的函数,h(u,j)=i,u∈U,i和j都是在范围[0,b)中的整数,b是A的规模。一般来说,我们使

    参考来源

    - 位置:《算法技术手册》第5章《变种》(spine1552;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1515.html;u132-ch05-009)。 - 结论依据:132全文、脚注及03266示意实读。 - 原始内容:开放定址的技术,这种技术直接将冲突元素存储在散列表A中。如图5-7所示。使用了开放定址技术,散列表减少了存储开销,例如在冲突的链表中使用指针指向元素。使用开放定址技术,我们将散列函数调整成为带两个参数的函数,h(u,j)=i,u∈U,i和j都是在范围[0,b)中的整数,b是A的规模。一般来说,我们使