3分钟带你读懂哈希、散列值、哈希表、消息摘要的核心逻辑，并掌握 4 种主流Hash碰撞解决策略。
1️⃣ 什么是 Hash算法？
Hash算法（又称散列算法）把任意长度输入通过散列函数变换成固定长度输出，这个输出就叫散列值或哈希值。
- 特点：定长、高效、不可逆。
- 关键词聚焦：哈希值、散列函数、消息摘要、单向运算。
2️⃣ Hash算法的两大主战场
2.1 数据结构：哈希表
哈希表（散列表）利用Hash算法把「关键字」映射到表中某一位置，实现O(1)平均时间复杂度的查找。
- 场景：缓存、计数器、去重集合。
- 弹性提示：此类场景更关心「运算速度」和「均匀分布」，抗碰撞性可适度放宽。
2.2 密码学：消息摘要与抗碰撞
在密码学领域，Hash算法被用作消息摘要，确保信息完整性。
能力要求：
- 不可逆：无法根据散列值反推原文。
- 高度抗碰撞：两段不同原文，几乎不可能产生相同散列值。
- 常用算法：SM3、MD5、SHA-1、SHA-256。
- 典型应用：数字签名、区块链区块哈希。
3️⃣ 哈希碰撞：为何会发生？如何判断？
不同输入经过相同散列函数后得到同一哈希值，即为哈希碰撞。
- 概率公式：
若哈希值长度为 16 位二进制，则碰撞概率为 1/65 536。当用户数超过 65 537 时，碰撞“板上钉钉”。 - 安全经济平衡：
把长度扩展到 32 位，可将概率降到 1/4 294 967 296，但会牺牲存储与计算资源。
4️⃣ 4 种常见哈希碰撞解决策略
4.1 开放地址法
一旦冲突，就在哈希表里继续找下一个“空位”。
- 线性探测：d_i = 1, 2, 3 …
- 二次探测：d_i = ±1², ±2², ±3², …（缓解堆积）
- 伪随机探测：d_i 取随机序列，跳跃地址更离散。
公式表示： Hi = (H(key) + d_i) MOD m
优点：无需额外空间。
缺点：容易产生“堆积”，导致连续占用。
4.2 再哈希法（双哈希法）
准备多个互不相同的散列函数 H₁、H₂、H₃…
冲突时顺次切换函数，直至无冲突。
优点：缓解聚集；缺点：计算量增加。
👉 想知道再哈希法让 HashMap 不“堵车”的幕后原理？
4.3 链地址法（Java HashMap 的实现）
把落在同一哈希桶的元素用单向链表串起来，碰撞自动变成链表操作。
优点：
- 实现简单，可动态扩容；
- 适合负载因子波动大的系统。
缺点：极端哈希分布下，链表过长会导致退化。
4.4 建立公共溢出区
为主哈希表和溢出区分别建数组：
- 主哈希表：正常使用；
- 溢出区：专门存冲突数据。
优点：思路清晰；缺点：需要额外空间，访问复杂度略高。
FAQ · 高频问答
Q1：SHA-256 真的比 MD5 安全吗？为什么？
A1：安全体现在抗碰撞能力。MD5 的 128 位输出已可利用「生日攻击」在 2^64 量级内找到碰撞，而 SHA-256 提供 256 位输出，计算成本指数级提升，抗碰撞性远超 MD5。
Q2：哈希表在高峰期出现“拥挤”，如何优雅扩容？
A2：业界常采用 扩大桶数 + 再哈希 并重写所有键值映射。主流语言或框架内置「负载因子」门限（如 0.75），超出触发自动 resize，通常一次扩容成本被摊销到 O(1)。
Q3：链地址法的链表可以换成红黑树吗？
A3：可以。当链表长度 > 阈值（Java 8 中为 8 且桶数 ≥ 64）时，自动转成红黑树，实现 O(log n) 的最坏查询复杂度，防止恶意哈希攻击。
Q4：为什么区块链交易必须引用交易哈希而非原文？
A4：利用消息摘要的小体积、唯一性优势，既保证完整性又节省区块链存储。
Q5：自己想动手写哈希函数要注意什么？
A5：若用于数据结构，重点确保 均匀分布；若用于密码学场景，务必采用经过验证的算法，拒绝“自创加密”。
5️⃣ 结语：安全与性能永远在做平衡
Hash算法的发展史，就是安全、性能、成本三者之间的反复博弈。
无论你是优化哈希表缓存，还是设计区块链共识，都需基于场景选算法、定长度、备碰撞方案。牢记：用好成熟的哈希函数，远比自己“拍脑袋”DIY 可靠。