哈希冲突怎么解决？链地址法和开放寻址法有什么区别？

知识点详解：同一个位置冲突以后，查找怎样继续

哈希函数只给位置，最终还要比较键

咱们假设两个字符串都映射到槽位 2。不能因为位置相同，就认为第二个覆盖第一个。

查找时必须比较实际键。哈希是一种定位方式，不是键的唯一身份。

OpenDSA 的哈希教材介绍了冲突与相关策略。实现还要保证等价键具有一致的哈希规则，否则插入和查找可能落在不同位置。

链地址法，把冲突留在桶里

数组的每个位置对应一个桶，冲突元素进入同一桶的结构。查找目标时，先根据哈希定位桶，再检查桶中的元素。

桶内部可以是链表，也可以采用其他结构，所以“链地址法永远是一条链表”过于绝对。不同语言和容器实现会有不同策略。

优势是冲突元素不必占用其他桶的位置；代价是额外结构、指针或内存分配。桶中的元素越来越多时，查找成本也可能增加。

开放寻址，把查找变成一条探测路径

假设采用线性探测，位置 2 已占用，就继续看 3、4 等位置。插入和查找必须采用相同规则。

查找目标时，遇到相同键就返回；遇到一个从未使用的空槽，可以判断后续不必继续。但遇到其他键，需要沿探测路径继续。

线性探测容易形成连续占用区域，增加探测长度；其他策略试图改善不同冲突模式，不过都要保证探测覆盖与终止条件。

删除标记为什么不能省略

咱们假设 A 和 B 都从位置 2 开始探测。A 放在 2，B 因冲突放在 3。

删除 A 后，如果把 2 直接标成“从未使用的空槽”，查 B 时会在 2 提前结束，误认为不存在。

常见做法是把 2 标成“已删除”。查找经过删除标记仍要继续；插入可以考虑复用，但还要检查后面是否已经存在同键，避免重复。

删除标记多了，也会增加探测成本，因此需要整理或重建。这是开放寻址维护的重要部分，不是一次 remove 就结束。

负载因子有用，但不能脱离实现看数字

负载因子通常描述元素数量与容量的关系。链地址法和开放寻址对高负载的承受方式不同；开放寻址还需要剩余槽位和合理探测策略。

扩容不是简单增加数组以后原样复制位置。容量改变时，键可能需要重新定位，迁移期间也要保持查找正确。

比较时应观察访问局部性、节点分配、删除频率、探测长度和扩容成本。数组连续访问可能更利于缓存，链地址结构可能更便于某些删除操作，但都不是绝对性能结论。

最坏情况下，碰撞集中会让性能退化。处理不可信输入时，还可能需要防范人为构造的碰撞，不能只报告平均复杂度。

面试官继续追问

哈希函数足够好，就不会冲突吗？

有限位置面对更多可能的键，冲突不可避免。好的函数改善分布，但不能取消冲突处理。

开放寻址的删除一定用墓碑吗？

不是唯一方案，也有后移等策略，但它们需要满足具体探测方式的正确性条件。不能随意删除后把后面所有元素移动一格。

为什么不把负载因子设得越小越好？

更低负载通常减少某些冲突，也会增加内存占用。应按访问模式和实现评估，而不是无限扩大数组。

面试速记卡

• 冲突本质：不同键定位到同一位置。
• 链地址：桶内继续比较实际键。
• 开放寻址：沿一致探测路径寻找其他槽位。
• 删除边界：空槽与已删除标记不能随意混用。
• 性能判断：分布、负载、删除与扩容共同影响。