知识卡片
删除标记使有效负载低估探查
删除使有效成员数下降,但留下的标记不会终止查询。经过很多插入/删除,即使当前size很小,也可能必须跨过许多删除槽,单用当前n/m预测探查成本会过于乐观。
本书进一步用“初始化以来最大负载”解释删除后的成本,也不足以覆盖所有历史:概念上可每次只插一个新键再删除,让不同槽依次留下标记;同时存活数量一直很低,标记仍能逐渐铺满表。这个反例按探查规则推导,未运行原源码。
分析需要同时考虑有效槽、删除标记、真正空槽及探查序列;没有重建就不能假定删除会把查询恢复到新空表状态。此处不补造实现中没有的自动重建机制。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
最大负载因子),这个常数值很小。为什么删除操作的性能由最大负载因子决定,而且不会随着删除元素而提高,是因为我们仍然会探查曾经删除过元素的槽。使用成员vacated只能提高ohtbl_insert的效率。
参考来源
- 位置:《算法精解:C语言描述》第8章《ohtbl_remove》(spine1281;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1248.html;u139-ch08-021)。
- 结论依据:139/140完整最大历史负载解释与135哨兵规则、02834实际移除写标记代码实读;反例是规则层面推导,不掩盖原lookup另有漏哨兵分支。
- 原始内容:最大负载因子),这个常数值很小。为什么删除操作的性能由最大负载因子决定,而且不会随着删除元素而提高,是因为我们仍然会探查曾经删除过元素的槽。使用成员vacated只能提高ohtbl_insert的效率。