7.5.4 散列查找及性能分析

教材导航 · 第7章

原书定位

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

装填因子 α=n/m\alpha=n/m。效率受散列函数、冲突处理与装填因子共同影响;通常 α\alpha 越大,冲突越多。

计算成功 ASL:从每个已存关键字的原散列地址,按探测规则数到其实际位置,再按查询概率加权。计算失败 ASL:从散列函数可能产生的各初始地址出发,数到首个真正空位或链尾,按这些初始地址的概率加权。

失败 ASL 的分母应取题设的散列初始地址范围,未必等于表长。开放定址中探到的记录可能不是同义词;拉链法同一桶的记录才有相同原散列值。多次逻辑删除后墓碑仍可能增加探测代价。

线性探测构造散列表

线性探测构造散列表,原书P326。

成功查找的逐项比较次数

成功查找的逐项比较次数,原书P326。

对应练习

7.5 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P326,PDF第338页

原书对照,原书P327,PDF第339页