7.5.3 拉链与开放定址

拉链法每桶保存冲突键链，删除直接摘链。开放定址把所有键放数组，线性探测h_i=(h+i)mod m，二次探测或双散列减少聚集。开放定址删除不能直接置空，应设墓碑，否则会截断后续键查找。

手工推演

m=7,h=k mod7，插10在3，17冲突放4，24放5。删17若把4置空，查24到4会误判失败；墓碑允许继续到5。

结构与代码

线性探测必须最多检查m个槽，避免满表死循环。拉链负载因子可大于1；开放定址通常需保持较低负载并定期重建清墓碑。

正确性

探测序列是插入和查找共同路径；遇真正空槽可判不存在，遇墓碑只能继续。

错解反馈

删除置空；探测不取模；二次探测未保证覆盖表；链表只比散列值不比原键。

迁移训练

上述表删除17后查24会检查哪些槽？答案3、4墓碑、5命中。