知识卡片
五独立限制线性探测
“五独立”指对任意五个不同键,它们的哈希槽联合分布与五次独立均匀选择相同。定理 11.9 给线性探测的期望常数操作时间附上明确条件:起始槽哈希函数族满足五独立,且元素数与槽数之比 α≤2/3。搜索、插入、删除都受此界约束。
一般开放寻址的理想随机探测分析不能直接替代这个条件。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
If h1 is 5-independent and α ≤ 2/3, then it takes expected constant time
参考来源
- 位置:《算法导论(第4版)》第 11 章定理 11.9(`OEBPS/chapter011.xhtml`,文本字符 [65000, 70000))。
- 结论依据:原文将线性探测的期望常数界明确限定在五独立及负载条件下,证明引自文献。
- 原始内容:If h 1 is 5-independent and α ≤ 2/3, then it takes expected constant time