知识卡片

普通读书笔记卡 · 3620.c.1.d.3.a

开放寻址探测随负载激增

理解等级:高级

无删除且满足理想随机探测时,设表中元素数为 n、槽数为 m,负载因子 α=n/m<1。失败查找及插入的期望探测数至多 1/(1−α)。

半满时上界 2,九成满时上界 10;接近满载成本急升。

成功查找还需额外假设已存键等可能被查询,不能混同失败查找界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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 − α )