hash冲突

在哈希表中，哈希冲突是指两个或多个不同的键被哈希到同一个位置（即哈希值相同）的情况。解决哈希冲突的方法有以下几种：

1. 开放寻址法 (Open Addressing)

• 基本原理: 当发生哈希冲突时，通过寻找下一个空闲的哈希表位置来存储冲突的键值对。常见的策略包括线性探测、二次探测和双重哈希。
• 查询时间:
  • 平均时间复杂度: ( O(1) )
  • 最坏时间复杂度: ( O(n) )，在哈希表接近满时，最坏情况下可能需要探查整个哈希表。

2. 链地址法 (Chaining)

• 基本原理: 每个哈希表的槽位保存一个链表（或其他数据结构），所有哈希到同一位置的键值对都存储在这个链表中。当发生冲突时，将新键值对追加到对应槽位的链表中。
• 查询时间:
  • 平均时间复杂度: ( O(1) )，假设哈希函数较好，链表长度较短。
  • 最坏时间复杂度: ( O(n) )，在极端情况下，所有键值对可能被哈希到同一槽位，此时需要遍历整个链表。

3. 再哈希法 (Rehashing)

• 基本原理: 在发生冲突时，应用另一个哈希函数对键进行再次哈希，直到找到空闲槽位。
• 查询时间:
  • 平均时间复杂度: ( O(1) )
  • 最坏时间复杂度: ( O(n) )，如果使用的哈希函数非常糟糕或者哈希表接近满。

4. 建立公共溢出区

• 基本原理: 哈希表的每个槽位存储一个指针，当发生冲突时，将冲突的键值对放到一个公共的溢出区中，而不是哈希表的槽位中。
• 查询时间:
  • 平均时间复杂度: ( O(1) )
  • 最坏时间复杂度: ( O(n) )，当所有键值对都哈希到相同位置，所有元素都存储在溢出区中。

总结：

• 最常用的方法: 链地址法（Chaining）是最常用的哈希冲突解决方法，因为它的实现简单，并且在负载因子不高时性能较好。
• 查询时间:
  • 平均查询时间: ( O(1) )，在大多数情况下，哈希表的查询时间非常高效。
  • 最坏查询时间: ( O(n) )，在极端情况下（例如哈希函数产生大量冲突），查询时间可能退化为线性时间。