7.5.3.1 开放定址法

教材导航 · 第7章

原书定位

印刷页P325起,对应PDF第337页。下文为目视整理的知识提要;完整内容见原书对照。

探测公式为 Hi=(H(key)+di) mod mH_i=(H(key)+d_i)\bmod m,原地址为第 0 次探测。

方法增量及性质
线性探测di=id_i=i,按环顺序扫描,易发生主聚集
平方探测如 ±12,±22,…\pm1^2,\pm2^2,\ldots,能否遍历全部槽位取决于表长及序列
双散列di=iH2(key)d_i=iH_2(key),步长非零且与 mm 互素可覆盖全表
伪随机探测使用确定且可复现的增量序列

查找必须按插入时的同一序列继续。删除通常留下墓碑标记,查询遇墓碑继续、遇从未使用的空位才可判失败;直接清空会截断其他记录的查找路径。还应限制最多探测范围,避免全表满时无限循环。

对应练习

7.5 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P325,PDF第337页