Hashtable哈希表如何处理冲突

在哈希表（Hashtable）中，当两个不同的键通过哈希函数计算出相同的索引时，就会发生冲突。为了处理这种冲突，可以采用以下几种方法：

1. 开放寻址法（Open Addressing）

开放寻址法是一种在哈希表内部解决冲突的方法。当发生冲突时，它会按照某种探测序列在哈希表中寻找下一个可用的槽位。

常见的开放寻址法包括：

• 线性探测（Linear Probing）：

  • 当发生冲突时，顺序查找下一个空槽位。
  • 公式：h(k, i) = (h(k) + i) % table_size，其中 h(k) 是原始哈希值，i 是探测次数。

• 二次探测（Quadratic Probing）：

  • 使用二次函数来计算探测步长，以减少聚集现象。
  • 公式：h(k, i) = (h(k) + c1 * i + c2 * i^2) % table_size。

• 双重哈希（Double Hashing）：

  • 使用第二个哈希函数来确定探测步长，确保每个键都能均匀分布。
  • 公式：h(k, i) = (h1(k) + i * h2(k)) % table_size，其中 h1(k) 和 h2(k) 是两个不同的哈希函数。

2. 链地址法（Chaining）

链地址法是在每个哈希表的槽位上维护一个链表（或其他数据结构如红黑树），所有映射到同一索引的元素都存储在这个链表中。

工作原理：

• 当插入一个新元素时，计算其哈希值并找到对应的槽位。
• 将新元素添加到该槽位的链表头部或尾部。
• 查找元素时，先找到对应的槽位，然后在链表中进行遍历查找。

3. 再哈希法（Rehashing）

再哈希法是在发生冲突时，使用另一个哈希函数来计算一个新的索引位置。

步骤：

1. 计算原始键的哈希值并找到初始槽位。
2. 如果该槽位已被占用，则使用再哈希函数计算新的索引。
3. 重复步骤2，直到找到一个空槽位。

4. 建立公共溢出区

这种方法将哈希表分为基本表和溢出表两部分：

• 基本表用于存储大部分元素。
• 溢出表用于存储发生冲突的元素。

选择合适的方法

• 开放寻址法适用于负载因子较低且表大小固定的情况。
• 链地址法适用于负载因子较高且插入、删除操作频繁的情况。
• 双重哈希法可以减少聚集现象，但实现相对复杂。
• 再哈希法和公共溢出区在实际应用中较少使用，因为它们的性能通常不如前两种方法。

注意事项

• 哈希表的大小通常是质数，以减少哈希冲突。
• 负载因子（即元素数量与表大小的比值）应控制在一定范围内，以保持良好的性能。
• 定期调整哈希表的大小（扩容或缩容）可以进一步优化性能。

通过合理选择和处理冲突的方法，可以显著提高哈希表的效率和可靠性。