哈希冲突处理

不同关键字映射到同一地址，称为冲突（Collision）。实用哈希表必须约定冲突处理策略。

哈希表整体见 哈希表。

本文解决什么问题

• 链地址与开放定址如何工作
• 删除时要注意什么
• 负载因子与扩容

链地址法（拉链法）

每个槽挂一条链表（或动态数组），冲突元素串在同一槽下。

• 实现清晰，装载因子较大时仍可用
• 最坏一条链很长 → $O(n)$；好哈希下接近 $O(1)$
• C++ unordered_map 等实现常用类似思想（细节依标准库）

开放定址法

冲突后在表内探查下一个空位：

方式	探查序列直觉
线性探查	$h, h+1, h+2, \ldots$
二次探查	$h, h+1^2, h+2^2, \ldots$
双重哈希	用第二个哈希函数决定步长

线性探查插入 key:
  i = h(key)
  while 槽 i 被其他 key 占用:
      i = (i + 1) % capacity
  放入 i

聚集（clustering）：线性探查易形成连续占用区，后来的冲突更严重。

删除要注意

不能简单置空：否则会打断探查链，导致后面的元素「找不到」。常见做法是标记删除（tombstone），查找时跳过，插入时可复用。

负载因子与扩容

$$\alpha = \frac{\text{元素个数}}{\text{容量}}$$

$\alpha$ 升高，冲突与探查变长。超过阈值（如 0.5～0.75，视实现而定）应扩容并重新哈希。

其他

再哈希、公共溢出区等。工程哈希还要考虑哈希质量、攻击下的最坏情况（有的实现会加盐或改用树化桶）。

小结

冲突不可避免，策略决定性能。先理解拉链与线性探查，再结合哈希表正文看完整例子。

下一章进入 排序概述。