什么是 Hash 碰撞？怎么解决哈希碰撞？表述通俗易于理解

通俗解释：Hash 碰撞与解决方法

什么是 Hash 碰撞？

想象你有一个大仓库（哈希表），每个货物（数据）都有一个编号（哈希值）。仓库规定：编号相同的货物必须放在同一个货架。

但有一天，两个不同的货物（比如 "苹果" 和 "香蕉"）被计算出了相同的编号（哈希值），它们都想挤进同一个货架——这就是 Hash 碰撞。

本质原因：

哈希函数将无限的可能输入（如所有字符串）映射到有限的输出范围（如固定长度的整数），必然存在多个不同输入对应同一输出的情况。

如何解决 Hash 碰撞？

1. 开放寻址法（Open Addressing）

• 核心思想：如果目标货架已满，就去隔壁找空位。
• 具体操作： 当插入数据时发现冲突，按某种规则（如线性探测、平方探测）寻找下一个空闲位置。例如：hash(key) + 1, hash(key) + 2……直到找到空位。
• 优点：数据直接存储在数组中，内存连续，缓存友好。
• 缺点：容易产生“聚集效应”（多个碰撞数据扎堆），查找效率可能下降。

2. 链地址法（Separate Chaining）

• 核心思想：让货架上挂一个篮子（链表/红黑树），所有冲突的货物都丢进这个篮子。
• 具体操作： 每个哈希桶（货架）维护一个链表，冲突的数据追加到链表末尾。Java 的 HashMap、Python 的字典均采用此方法（链表过长时转为红黑树优化）。
• 优点：实现简单，适合频繁插入删除的场景。
• 缺点：链表过长时查询效率低（需遍历链表）。

3. 再哈希法（Double Hashing）

• 核心思想：第一次哈希冲突后，换另一个哈希函数重新计算位置。
• 具体操作： 定义一组不同的哈希函数，依次尝试直到找到空位。
• 优点：减少聚集效应。
• 缺点：计算成本较高，需设计多个优质哈希函数。

4. 公共溢出区法

• 核心思想：单独划出一块区域存放所有冲突的数据。
• 具体操作： 主哈希表正常插入，冲突数据统一存放到另一个独立区域（如另一个数组）。
• 优点：实现简单。
• 缺点：溢出区过大时效率急剧下降。

实际应用中的选择

• 小规模数据：开放寻址法（如 Redis 字典）。
• 高频插入/删除：链地址法（如 Java HashMap）。
• 极致性能要求：结合链地址法与红黑树（防止链表过长）。

一句话总结

Hash 碰撞是不同数据算出相同哈希值的“撞车”现象，解决方法本质是要么另找车位（开放寻址），要么排队共存（链地址）。