开放寻址处理冲突
复习
- 哈希函数与哈希表：根据键直接算出位置
- 拉链法：用链表格外串联冲突元素
- 数组：连续存储，可按位置访问
TL;DR
- 开放寻址不额外用链表，而是在表内继续找空位
- 常见探测方式：线性探测、二次探测、双重哈希
- 它省去指针开销，对缓存更友好
- 但删除麻烦，还容易出现“聚堆”
正文
拉链法靠额外的链表来安置冲突元素。另一派思路是：所有元素都放在表本身里，位置被占了，就按规则继续找下一个空位。 这叫开放寻址（open addressing）。
位置被占，就另找一个
开放寻址的基本动作是：
- 用哈希函数算出理想位置
- 如果那个位置已经有人，就按某种探测规则，依次试下一个位置
- 直到找到空位放进去
查找时同理：先算位置，不对就按同样的规则一路找下去，直到找到目标或遇到空位。
常见的探测规则有：
- 线性探测：位置被占，就试下一个、再下一个
- 二次探测：按平方的间隔跳着试，避免挤在一起
- 双重哈希：再用第二个哈希函数决定“每次跳多远”
好处与麻烦
开放寻址的最大好处，是不需要额外的指针。所有数据都挨在同一个数组里，内存更紧凑，对 CPU 缓存也更友好——这在追求性能的场合很关键。
但它也有两个麻烦：
- 聚堆：线性探测尤其容易出现“越挤越挤”的现象。一旦某个区域被占满，后面的元素更容易连成一片，查找时就要一路走过长长的占用区
- 删除难：不能简单地把元素清空，否则会打断后面元素的探测链。通常要打一个特殊的“墓碑”标记，表示“这里曾经有元素，但已删除，请继续往后找”
所以，开放寻址在实现上，比拉链法要更小心一些。
两种办法的取舍
把两者放在一起看：
- 拉链法：额外链表，删除方便，但多花指针空间
- 开放寻址：无额外结构，缓存友好，但删除麻烦、易聚堆
又一次熟悉的取舍：没有白来的好处，选择取决于你更在意空间、删除的便利，还是缓存性能。
思考题 1
开放寻址与拉链法在“冲突元素放在哪”这件事上，有什么根本不同？
思考题 2
为什么开放寻址在删除元素时，通常要打一个“墓碑”标记？
小结
知识点
- 开放寻址在表内按探测规则寻找空位
- 线性探测、二次探测、双重哈希是常见方式
- 它无指针开销、缓存友好
- 但存在聚堆问题，删除需借助墓碑标记
参考资料
- Wikipedia(zh)：开放寻址法：在表内寻找空位处理冲突
- Wikipedia(zh)：哈希表：比较不同冲突处理策略
思考题答案（仅供参考）
思考题 1
拉链法把冲突元素放到原位置之外的链表节点里，表只存“桶”；开放寻址则把冲突元素继续放在表本身中的其他空位，不引入额外结构。一个是“外挂”，一个是“就地另找”。
思考题 2
因为查找依赖探测链：从理想位置一路往后找。如果直接清空被删元素，探测链就断了，后面本应能通过继续探测找到的元素可能找不到。留一个“墓碑”标记，表示这里已删但仍需继续探测，从而不破坏查找的正确性。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪