解决哈希冲突是设计哈希表时的一个重要问题。因为哈希函数的输出是有限的，而输入的数据可能是无限的，因此不同的输入可能会被哈希到相同的位置（即发生冲突）。为了解决这个问题，常用的解决策略主要有两种：链式法（Chaining） 和 开放地址法（Open Addressing）。下面详细介绍这两种方法及其变种。

1. 链式法（Chaining）

概念：
链式法通过在哈希表的每个槽（或桶）中存储一个链表（或其他数据结构）来解决哈希冲突。如果两个元素的哈希值相同（发生冲突），它们将被存储在同一个槽中的链表里，而不是直接覆盖。

工作原理：

  • 哈希表中的每个位置存储一个链表的头指针。
  • 当发生冲突时，新的元素会被添加到对应槽的链表中。

优点：

  • 实现简单，容易理解。
  • 即使哈希表容量已满，冲突的元素也可以继续存储在链表中，不会丢失数据。
  • 没有聚集问题。

缺点：

  • 如果发生大量冲突，链表的长度会增加，导致查找的时间复杂度增大。最坏情况下，如果所有元素都哈希到同一个位置，查找时间复杂度变为 O(n)（其中 n 是元素数量）。

示例：

// 假设哈希表的大小是 10，使用链表解决冲突
哈希表： [null, null, [(12, "A"), (22, "B")], null, null, null, null]

在这个例子中，键 12 和键 22 都被映射到位置 2，它们通过链表存储。

2. 开放地址法（Open Addressing）

概念：
开放地址法通过探测（probe）空槽来解决冲突。即，当哈希函数计算的槽已经被占用时，开放地址法会根据某种策略（如线性探测、二次探测、双重哈希等）查找下一个空的槽，并将元素存储到该槽中。

常见的探测方法：

  1. 线性探测（Linear Probing）：
  • 如果发生冲突，检查当前位置的下一个位置。如果下一个位置也被占用，再检查下一个位置，以此类推，直到找到一个空的位置。
  • 探测公式：index = (hash(K) + i) % table_size，其中 i 是探测的步数，i = 0, 1, 2, ...。

优点：简单，易于实现。
缺点：可能出现聚集问题（Clustering），即多个元素可能聚集在哈希表的相邻位置，导致性能下降。

  1. 二次探测（Quadratic Probing）：
  • 在发生冲突时，按二次方的步长来探测下一个位置：index = (hash(K) + i^2) % table_size。
  • 这种方法避免了线性探测中的聚集问题，但它依然可能导致某些槽位无法被使用。

优点：减少了线性探测的聚集问题。
缺点：有时仍然可能会发生二次聚集，并且需要额外的计算。

  1. 双重哈希（Double Hashing）：
  • 使用第二个哈希函数来计算步长，避免了线性和二次探测的聚集问题。
  • 探测公式：index = (hash1(K) + i * hash2(K)) % table_size，其中 hash1(K) 是初始哈希值，hash2(K) 是第二个哈希函数。

优点：能有效避免聚集问题。
缺点：需要设计多个哈希函数。

优点：

  • 空间利用率较高，所有元素都存储在数组中，不需要额外的空间来存储链表。
  • 相对来说，对于一些冲突较少的场景，性能较高。

缺点：

  • 可能会发生聚集问题（尤其是线性探测）。
  • 如果负载因子过高，性能会下降。
  • 扩容时需要重新哈希所有元素。

示例：
假设哈希表的大小为 10，使用线性探测来解决冲突：

  1. 假设我们插入 key = 12，哈希值 hash(12) = 2，插入到槽 2。
  2. 接着插入 key = 22，哈希值 hash(22) = 2，发生冲突。使用线性探测，检查槽 3，如果 3 是空的，就将 22 插入到槽 3。
哈希表： [null, null, (12, "A"), (22, "B"), null, null, null]

3. 再哈希（Rehashing）

无论是链式法还是开放地址法，都可能在哈希表中元素越来越多时导致性能下降。此时通常会进行 扩容 和 再哈希，即：

  • 扩容：当负载因子（元素数量与表大小的比例）超过一定阈值时，增加哈希表的大小，通常是原大小的两倍。
  • 再哈希：扩容后，需要重新计算每个元素的哈希值，并将它们重新插入新的哈希表中。

再哈希是避免哈希冲突影响性能的重要手段。

总结：哈希冲突解决方法

  1. 链式法（Chaining）：使用链表存储冲突的元素，简单易实现，适合处理高冲突的场景。
  • 优点：容易实现，冲突处理不受限制。
  • 缺点：在冲突较多时，可能会导致查找性能下降。
  1. 开放地址法（Open Addressing）：通过探测下一个空槽解决冲突，减少空间消耗。
  • 优点：高效的空间利用率，不需要额外的空间来存储链表。
  • 缺点：可能会遇到聚集问题，且扩容时需要重新哈希。
  1. 再哈希（Rehashing）：当负载因子过高时，进行哈希表扩容和元素重新哈希，减少冲突对性能的影响。