知识卡片
线性探测只改起点
线性探测是步长固定为 1 的双重哈希:从 h₁(k) 开始逐槽向后查,抵达表尾后回绕。
所有键只因起点不同而有 m 种探测序列,少于一般双重哈希的多种起点与步长组合;它实现简单,但不能假定满足理想的随机置换探测模型。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 线性探测只改起点
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
Linear probing, a special case of double hashing, is the simplest open-addressing approach to resolving collisions.
参考来源
- 位置:《算法导论(第4版)》第 11 章 11.4 节(`OEBPS/chapter011.xhtml`,文本字符 [51500, 55000))。
- 结论依据:原文将线性探测定义为 h₂(k)=1,并比较其可生成探测序列数与理想模型。
- 原始内容:Linear probing , a special case of double hashing, is the simplest open-addressing approach to resolving collisions.