知识卡片
开放寻址探测随负载激增
无删除且满足理想随机探测时,设表中元素数为 n、槽数为 m,负载因子 α=n/m<1。失败查找及插入的期望探测数至多 1/(1−α)。
半满时上界 2,九成满时上界 10;接近满载成本急升。
成功查找还需额外假设已存键等可能被查询,不能混同失败查找界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
the expected number of probes in an unsuccessful search is at most 1/(1 − α)
参考来源
- 位置:《算法导论(第4版)》第 11 章定理 11.6、推论 11.7 与定理 11.8(`OEBPS/chapter011.xhtml`,文本字符 [54000, 60000);Art_P397–P400)。
- 结论依据:原文由连续占用槽概率界定失败探测并推出插入界,另列成功查找的查询分布前提。
- 原始内容:the expected number of probes in an unsuccessful search is at most 1/(1 − α )