散列表、冲突处理与装填因子

考点定位

本课深化 散列表、冲突处理与装填因子。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

散列性能取决于散列函数、装填因子和冲突处理。开放定址删除需墓碑标记；链地址法把同槽关键字组织成链。

算法推演

线性探测从h(k)开始依次检查(h(k)+i) mod m，查找失败必须按同一探测序列直到空槽；不能在被删除槽直接停止。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

插入和查找使用完全一致的探测序列，表未满时必能遇到可用槽。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：开放定址装填因子接近1时聚集和探测次数通常显著增加。

随课应用

表长7，h(k)=k mod 7，依次插入10、17、24并线性探测。成功查找24需要比较多少次？

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。