7.5.3.2 拉链法
原书定位
印刷页P325起,对应PDF第337页。下文为目视整理的知识提要;完整内容见原书对照。
每个散列地址对应一条链,同义词存入同一链。查找先定位桶,再逐个比较链中关键字;删除可直接摘链结点,不会截断其他桶的探测路径。
链内头插或尾插会改变成功查找比较次数。计数时空桶通常比较 0 个记录,非空桶失败需比较整条链;若题目按访问次数计空指针,应按题意另计。装填因子可以超过 1。

拉链法处理冲突的散列表,原书P326。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P325起,对应PDF第337页。下文为目视整理的知识提要;完整内容见原书对照。
每个散列地址对应一条链,同义词存入同一链。查找先定位桶,再逐个比较链中关键字;删除可直接摘链结点,不会截断其他桶的探测路径。
链内头插或尾插会改变成功查找比较次数。计数时空桶通常比较 0 个记录,非空桶失败需比较整条链;若题目按访问次数计空指针,应按题意另计。装填因子可以超过 1。

拉链法处理冲突的散列表,原书P326。

