知识卡片
开放定址依赖探测与删除规则
开放定址将元素放入桶数组的槽中;查找沿与插入一致的探测序列前进,遇到从未使用的空槽才可判定不存在。删除不能简单地把已使用槽改为从未使用,否则会截断后续元素的探测链;可使用删除标记或合适的回填策略。
线性探测可能产生聚集,二次探测需要参数和表容量满足覆盖要求;容量接近满时探测成本上升。书中探测次数公式是特定均匀散列模型下的期望界,不是所有实现的最坏界;最坏可扫描 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的规模。一般来说,我们使