哈希冲突解决方法

1. 分离链接法（Separate Chaining）

• 在每个哈希表的槽（桶）中维护一个链表、向量或其他数据结构，以存储多个键-值对。
• 当哈希冲突发生时，新的键-值对被添加到槽中的链表中。这种方法不会影响哈希表的性能，因为查找、插入和删除操作都可以在链表中进行。
• 这是一种简单且常用的方法，但如果链表变得过长，会降低性能。

2. 线性探测法（Linear Probing）

• 在发生哈希冲突时，线性探测法尝试将键-值对插入到下一个可用的槽。
• 当查找元素时，如果槽中没有目标元素，算法将线性地探测下一个槽，直到找到目标元素或者遇到一个空槽。
• 这种方法在一定程度上避免了链表的使用，但可能会导致聚集问题，即连续的槽可能会被占用，导致性能下降。

3. 双重哈希（Double Hashing）

• 双重哈希是一种改进的线性探测方法，其中线性探测的步长是通过第二个哈希函数计算的。
• 这可以更有效地解决哈希冲突，减少聚集问题。

4. 开放寻址法（Open Addressing）

• 开放寻址法是一种通用的方法，它包括线性探测、二次探测、双重哈希等技术。
• 在开放寻址法中，冲突后的键-值对被插入到另一个可用槽，而不是一个链表中。
• 这种方法的主要优点是不需要维护链表，但需要选择适当的探测方法，以避免产生聚集问题。