7.5.3.1 开放定址法
原书定位
印刷页P325起,对应PDF第337页。下文为目视整理的知识提要;完整内容见原书对照。
探测公式为 ,原地址为第 0 次探测。
| 方法 | 增量及性质 |
|---|---|
| 线性探测 | ,按环顺序扫描,易发生主聚集 |
| 平方探测 | 如 ,能否遍历全部槽位取决于表长及序列 |
| 双散列 | ,步长非零且与 互素可覆盖全表 |
| 伪随机探测 | 使用确定且可复现的增量序列 |
查找必须按插入时的同一序列继续。删除通常留下墓碑标记,查询遇墓碑继续、遇从未使用的空位才可判失败;直接清空会截断其他记录的查找路径。还应限制最多探测范围,避免全表满时无限循环。
对应练习
关联知识
原书对照
展开原书对照截图
