在哈希表中，哈希冲突是指两个或多个不同的键被哈希到同一个位置（即哈希值相同）的情况。

解决哈希冲突的方法有以下几种：

一、开放寻址法

 (Open Addressing)

基本原理：当发生哈希冲突时，通过寻找下一个空闲的哈希表位置来存储冲突的键值对。常见的策略包括线性探测、二次探测和双重哈希。

查询时间：

• 平均时间复杂度：( O(1) )

• 最坏时间复杂度：( O(n) )，在哈希表接近满时，最坏情况下可能需要探查整个哈希表。

二、链地址法

 (Chaining)

基本原理：每个哈希表的槽位保存一个链表（或其他数据结构），所有哈希到同一位置的键值对都存储在这个链表中。当发生冲突时，将新键值对追加到对应槽位的链表中。

查询时间：

• 平均时间复杂度：( O(1) )，假设哈希函数较好，链表长度较短。

• 最坏时间复杂度：( O(n) )，在极端情况下，所有键值对可能被哈希到同一槽位，此时需要遍历整个链表。
  

三、再哈希法

 (Rehashing)
基本原理：在发生冲突时，应用另一个哈希函数对键进行再次哈希，直到找到空闲槽位。

查询时间：

• 平均时间复杂度：( O(1) )

• 最坏时间复杂度：( O(n) )，如果使用的哈希函数非常糟糕或者哈希表接近满。
  

四、建立公共溢出区

基本原理：哈希表的每个槽位存储一个指针，当发生冲突时，将冲突的键值对放到一个公共的溢出区中，而不是哈希表的槽位中。

查询时间：

• 平均时间复杂度：( O(1) )

• 最坏时间复杂度：( O(n) )，当所有键值对都哈希到相同位置，所有元素都存储在溢出区中。

五、总结

最常用的方法：链地址法（Chaining）是最常用的哈希冲突解决方法，因为它的实现简单，并且在负载因子不高时性能较好。

查询时间：

• 平均时间复杂度：( O(1) )，在大多数情况下，哈希表的查询时间非常高效。

• 最坏时间复杂度：( O(n) )，在极端情况下（例如哈希函数产生大量冲突），查询时间可能退化为线性时间。