解决哈希冲突

哈希冲突是指在使用哈希函数将数据映射到哈希表时，不同的输入数据被映射到同一个哈希值的情况。哈希冲突会对哈希表的性能、数据完整性和安全性等方面造成多种危害，以下列方法解决哈希冲突。

开放寻址法

核心思想：当发生冲突时，通过某种探测策略在哈希表中寻找下一个空闲的槽位，直到找到为止。

探测序列是这种方法的关键，即如何计算下一个要探测的位置。公式通常为：
new_index = (hash(key) + probe(i)) % table_size，其中 probe(i) 是探测函数，i 是尝试次数。

常见的探测方法有：
线性探测

• 方法：探测函数是线性的，通常是 probe(i) = i。即如果原始位置 index 被占用，就依次检查 index+1, index+2, index+3 … 直到找到空位。

• 优点：实现简单。

• 缺点：容易产生聚集现象。即连续被占用的槽位会形成一片，导致后续 key 的查找时间变长。

平方探测

• 方法：探测函数是二次函数，例如 probe(i) = i² 或 probe(i) = (-1)^(i+1) * ceil(i/2)²。即探测的步长是平方数：index + 1², index - 1², index + 2², index - 2² …

  • 例如：第一次寻到的位是1，第二次为2，第三次为4……则这个寻找的步长为 i²，当然探测的步长不唯一，这里就是举个例子。

• 优点：避免了线性探测的聚集问题，是一种常见的开放寻址法。

• 缺点：不一定能探测到整个哈希表的所有位置（取决于表大小和探测函数）。

双重哈希

• 方法：使用两个哈希函数。第一个哈希函数 hash1(key) 计算初始位置。如果发生冲突，则由第二个哈希函数 hash2(key) 计算探测的步长：new_index = (hash1(key) + i * hash2(key)) % table_size。

• 优点：提供了最好的分布性，不容易产生聚集。不同的 key 具有不同的步长。

• 缺点：计算量稍大。

• 思想：如果第一个哈希函数给出的位置被占了，我不再固定地“走1步”或“走4步”，而是让“第二个哈希函数”来告诉我“每次走几步”。这样，不同的 key 在冲突时，它们的“步长”是不同的，从而最大限度地避免了“扎堆”（聚集）的问题。

例如：

• 哈希表大小： table_size = 7

• 键： key1 = 15, key2 = 8, key3 = 22

• 第一个哈希函数： hash1(key) = key % 7

• 第二个哈希函数： hash2(key) = 5 - (key % 5) （这是一个常见的构造方式，目的是得到一个与第一个函数不同且不为0的步长）

插入过程：
插入 key1 = 15

• index1 = hash1(15) = 15 % 7 = 1

• 位置 1 是空的，直接放入。表[1] = 15

插入 key2 = 8

• index1 = hash1(8) = 8 % 7 = 1

• 位置 1 已经被 15 占了！发生冲突。

• 现在启动双重哈希机制。计算步长：
  step = hash2(8) = 5 - (8 % 5) = 5 - 3 = 2

• 计算新位置： new_index = (1 + 1 * 2) % 7 = 3 % 7 = 3 （i=1是第一次尝试）

• 位置 3 是空的，所以放入。表[3] = 8

插入 key3 = 22

• index1 = hash1(22) = 22 % 7 = 1

• 位置 1 又被占了！再次冲突。

• 计算它的步长（注意，步长是 key 特有的）：
  step = hash2(22) = 5 - (22 % 5) = 5 - (2) = 3

• 开始探测：

  • 第一次尝试 (i=1): (1 + 1 * 3) % 7 = 4 % 7 = 4。位置 4 是空的，成功插入！表[4] = 22
    

为什么这样更好？
想象一下，如果用线性探测（每次走1步），15, 8, 22 都会挤在索引 1, 2, 3 的位置，形成“聚集”。
而在双重哈希中：

• 8 的步长是 2，它跳到了 3。

• 22 的步长是 3，它跳到了 4。
  它们分散开了。即使很多 key 都在第 1 个位置冲突，但因为它们的 hash2(key) 不同，步长就不同，会像不同方向弹开一样，探测路径不会重合，有效避免了聚集。

开放寻址法的共同特点：

• 负载因子：表中的元素数 / 表的大小。负载因子不能超过 1（即元素数不能超过数组容量）。当负载因子较高时（例如 > 0.7），性能会急剧下降，必须进行扩容（Rehashing）。

负载因子不能超过 1，且对性能至关重要

• 什么是负载因子？ 负载因子 = 已存放元素个数 / 哈希表总大小。

  • 例如，一个大小为 10 的哈希表，插入了 7 个元素，它的负载因子就是 0.7。

• 为什么不能超过 1？ 开放寻址法的“地址”就是数组的索引。数组只有 10 个位置，你不可能放下 11 个元素。这是物理限制。

• 对性能的影响： 随着负载因子增大，空闲位置越来越少，发生冲突的概率越来越高。每次插入或查找，需要探测的次数也急剧增加。

  • 当负载因子达到 0.7 或 0.8 左右时，性能就已经变得很差了。

解决方案：扩容（Rehashing）

• 当负载因子超过某个阈值（例如 0.7），就必须对哈希表进行扩容。

• 创建一个新的、更大的数组（通常是原来的 2 倍左右）。

• 遍历旧数组中的每一个元素。

• 用相同的哈希函数，但对新数组的大小取模，为每个元素重新计算一个在新数组中的位置。

• 将它们插入到新数组中。
  这个过程是开销很大的，但又是必要的。

• 删除操作：不能简单地置空槽位，否则会中断探测序列，导致后续元素无法被查找到。通常采用“懒删除”策略，用一个特殊的标记（如 TOMBSTONE）标记已删除的位置。

问题所在： 假设我们依次插入了 A 和 B，B 因为和 A 冲突，通过探测放到了下一个位置。现在我们要删除 A。

• 如果我们简单地把 A 的位置置为空（NULL）。

• 之后我们来查找 B。我们先计算 B 的哈希值，找到了原来 A 的位置，发现这里是“空”！

• 程序会错误地认为“B不存在”，因为开放寻址法的规则是“遇到空位就停止探测”。而真正的 B 还在后面的位置，但探测路径被这个空位中断了。

解决方案：懒删除
我们不在删除时立刻清空位置，而是用一个特殊的、唯一的标记（通常叫 TOMBSTONE 或 DELETED）来标记这个位置。

• 插入时：遇到 TOMBSTONE 位置，可以把它当作一个可用的空位，直接插入。这可以复用被删除的空间。

• 查找时：遇到 TOMBSTONE 位置，不能停下，必须继续向后探测，直到找到目标或遇到真正的 NULL。

这样，探测路径就不会被中断，可以正确找到后面的元素 B。

链地址法

核心思想：不寻找下一个空位，而是将哈希到同一槽位的所有元素存放在一个链表中。哈希表的每个槽位（bucket）都是一个链表的头指针。

方法：插入时，计算出哈希值后，直接将该键值对插入到对应链表中（可以是链表头部，操作是 O(1)）。查找和删除时，也是先找到对应链表，再在链表中进行遍历操作。

优点：

• 实现简单，逻辑清晰。

• 有效缓解冲突，负载因子可以大于 1。

• 删除操作简单，直接从链表中删除节点即可。

缺点：

• 需要额外的空间存储指针。

• 如果某个链表非常长，查询效率会退化为 O(n)。（好的哈希函数可以缓解这一问题）

• 优化：在现代编程语言（如 Java 的 HashMap）中，当链表长度超过一定阈值（如 8）时，会将其转换为红黑树，以确保最坏情况下的时间复杂度为 O(log n)。

这是最常用、最经典的方法。

例如：

假设我们有一个哈希表，大小为 5（即有 5 个槽位 [0] 到 [4]）。
我们的哈希函数非常简单：hash(key) = key % 5（键除以 5 取余数）。

现在，我们依次插入以下键：12, 8, 10, 3, 23, 15。

第1步：插入 12

• hash(12) = 12 % 5 = 2

• 放入槽位 2。

索引:   0     1     2     3     4
      [ ]  [ ]  [12]  [ ]  [ ]

第2步：插入 8

• hash(8) = 8 % 5 = 3

• 放入槽位 3。

索引:   0     1     2     3     4
      [ ]  [ ]  [12]  [8 ]  [ ]

第3步：插入 10

• hash(10) = 10 % 5 = 0

• 放入槽位 0。

索引:   0     1     2     3     4
      [10] [ ]  [12]  [8 ]  [ ]

第4步：插入 3

• hash(3) = 3 % 5 = 3

• 冲突！ 槽位 3 已经被 8 占用了。

• 链地址法处理：将 3 作为新节点，添加到槽位 3 的链表头部（或尾部）。

索引:   0     1     2     3     4
      [10] [ ]  [12]  [8 ]  [ ]
                    |
                    [3 ]  // 新节点连接到8后面

第5步：插入 23

• hash(23) = 23 % 5 = 3

• 再次冲突！ 槽位 3 已经有一个链表 8 -> 3。

• 将 23 添加到这个链表的头部。

索引:   0     1     2     3     4
      [10] [ ]  [12]  [23]  [ ]
                    |
                    [8 ]
                    |
                    [3 ]

(另一种常见画法，更清晰地表示链表)

索引:   0     1     2     3     4
      [10] [ ]  [12]  [8 ]  [ ]
                    |\
                    | \
                    [3] \
                     |
                    [23]

第6步：插入 15

• hash(15) = 15 % 5 = 0

• 冲突！ 槽位 0 已经被 10 占用了。

• 将 15 添加到槽位 0 的链表中。

索引:   0     1     2     3     4
      [10] [ ]  [12]  [8 ]  [ ]
       |\          |\
       | \         | \
      [15] \      [3] \
                    |
                   [23]

最终哈希表示意图

索引:   值 (链表形式)
-------------------
[ 0 ]  --> [10] --> [15] --> NULL
[ 1 ]  --> NULL
[ 2 ]  --> [12] --> NULL
[ 3 ]  --> [8] --> [3] --> [23] --> NULL
[ 4 ]  --> NULL

这个示意图的解释：

• 数组（哈希表）：最左边的一列 [0] 到 [4] 是哈希表的底层数组，每个位置是一个“桶”或“槽位”。

• 链表：每个槽位指向一个链表。例如，槽位 [3] 指向一个链表，里面包含了 8, 3, 23 这三个元素。

• 冲突解决：所有哈希值为 3 的键（8, 3, 23）都被“链”在了同一个链表里，而不是丢失或者挤占其他空位。查找时，先通过 hash(key) 快速定位到槽位 [3]，然后再遍历这个短链表来找到目标值。

• 空槽位：槽位 [1] 和 [4] 是空的，它们指向 NULL。

其他方法

再哈希法

• 准备一组哈希函数 hash1(key), hash2(key), hash3(key)…。

• 如果 hash1(key) 发生冲突，就尝试 hash2(key)，如果再冲突，就尝试 hash3(key)，直到找到空位。

• 这种方法不容易产生聚集，但计算时间较长。

建立公共溢出区

• 将哈希表分为两部分：基本表和溢出表。

• 当发生冲突时，将所有冲突的键值对都放入溢出表中。

• 查找时，先在基本表中定位，如果没找到，再去溢出表中顺序查找。

• 这种方法适用于冲突数据较少的情况。

小结

在实际应用中，链地址法通常是首选，因为它简单、稳定，并且在负载因子较高时性能下降更平缓。而开放寻址法在需要节省内存（因为不需要指针）或者数据记录较小时可能更有优势。