7.5.4 散列查找及性能分析
原书定位
印刷页P326起,对应PDF第338页。下文为目视整理的知识提要;完整内容见原书对照。
装填因子 。效率受散列函数、冲突处理与装填因子共同影响;通常 越大,冲突越多。
计算成功 ASL:从每个已存关键字的原散列地址,按探测规则数到其实际位置,再按查询概率加权。计算失败 ASL:从散列函数可能产生的各初始地址出发,数到首个真正空位或链尾,按这些初始地址的概率加权。
失败 ASL 的分母应取题设的散列初始地址范围,未必等于表长。开放定址中探到的记录可能不是同义词;拉链法同一桶的记录才有相同原散列值。多次逻辑删除后墓碑仍可能增加探测代价。

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

成功查找的逐项比较次数,原书P326。
对应练习
关联知识
原书对照
展开原书对照截图

