C++ Hash表与哈希冲突处理

在C++中，哈希表是一种数据结构，它提供了快速的插入、删除和查找操作。哈希表通过将关键字（key）映射到表中一个位置来存储数据。这个映射是通过哈希函数（hash function）实现的。然而，当两个不同的关键字具有相同的哈希值时，就会发生哈希冲突（hash collision）。为了解决这个问题，有以下几种常见的哈希冲突处理方法：

1. 链地址法（Separate Chaining）： 在这种方法中，哈希表的每个槽位都包含一个链表。当发生哈希冲突时，将具有相同哈希值的元素添加到该槽位的链表中。查找和删除操作需要遍历链表。这种方法的优点是简单易实现，缺点是链表可能会变得很长，导致性能下降。

2. 开放寻址法（Open Addressing）： 开放寻址法是一种线性探测（linear probing）或二次探测（quadratic probing）的方法。当发生哈希冲突时，根据一定的规则在哈希表中寻找下一个可用的槽位。线性探测是每次冲突后，按照固定的步长（如1）寻找下一个槽位；二次探测是在冲突后，按照当前槽位与目标槽位之间的距离进行平方后寻找下一个槽位。开放寻址法的优点是解决了链地址法中链表过长的问题，缺点是实现起来较为复杂。

3. 再哈希法（Rehashing）： 再哈希法是使用多个哈希函数，当第一个哈希函数发生冲突时，尝试使用第二个哈希函数，以此类推。这种方法可以降低哈希冲突的概率，但需要更多的哈希函数和更大的哈希表。

4. 建立公共溢出区： 将哈希表分为基本表和溢出表两部分。当基本表中发生冲突时，将元素存储在溢出表中。这种方法需要额外的存储空间，但可以降低冲突的概率。

在实际应用中，可以根据具体需求和场景选择合适的哈希冲突处理方法。