1.50、哈希碰撞的处理方法

开放定址法（Open Addressing）

当发生碰撞时，通过探查（Probing）寻找下一个空闲槽位存储数据。常用探查方式包括：

• • 线性探查（Linear Probing）：依次检查后续槽位，简单但易产生“主聚集”问题。
• • 二次探查（Quadratic Probing）：探查间隔按二次函数增长，缓解聚集但实现稍复杂。
• • 双重哈希（Double Hashing）：用第二个哈希函数确定探查步长，有效减少聚集但计算开销较大。
  优点：所有数据存储在同一表内，缓存友好。
  缺点：表满时性能下降明显，删除操作复杂。

链地址法（Separate Chaining）

每个哈希槽维护一个链表（或其他动态结构），所有哈希值相同的元素链接在一起。插入时直接添加到链表头或尾。
优点：实现简单，表容量不易满，支持动态扩展，删除方便。
缺点：链表结构导致缓存性能较差，最坏情况下查找为O(n)。

再哈希法（Rehashing）

设计多个哈希函数，发生碰撞时依次尝试不同哈希函数计算的新地址，直到找到空槽。
优点：减少聚集现象，提高分布均匀性。
缺点：计算开销增加，复杂度提升。

公共溢出区法（Overflow Area）

将哈希表划分为基本表和溢出表，冲突元素存放在溢出区，类似链地址法但溢出区为独立空间。
优点：管理冲突集中，便于维护。
缺点：实现复杂，访问溢出区增加额外开销。

总结

• • 在C++中，链地址法是最常用且稳定的方案，结合STL的std::list或std::forward_list实现链表，代码简洁且易维护。
• • 开放定址法适合表大小固定且负载因子较低的场景，需谨慎设计哈希函数和探查策略。
• • 对于性能敏感场景，可结合缓存友好的开放定址与链地址法的优点，或采用动态扩容和再哈希策略。

面试时，除了描述方法，还应能分析各自的时间复杂度、空间开销及适用场景，体现对实际工程权衡的理解。
综上，哈希碰撞处理的核心在于权衡时间复杂度、空间利用率和实现复杂度。链地址法和开放定址法是最基础且广泛应用的两种方法，再哈希和公共溢出区则是针对特定需求的优化策略。
本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）