《Hello 算法》哈希算法深度解析：从哈希函数设计到工程实践

《Hello 算法》哈希算法深度解析：从哈希函数设计到工程实践

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本文以《Hello 算法》（hello-algo）开源仓库中 ru/docs/chapter_hashing/hash_algorithm.md 为主体，系统讲解哈希算法（Hash Algorithm）的设计目标、简单哈希构造方法、取模大质数的原理、主流哈希算法对比，以及各编程语言内置哈希的实现差异。读者学完本文，将能理解哈希函数为何是哈希表性能的"灵魂"，掌握从"解决冲突"到"减少冲突"的设计思路转变，并能在实际工程中正确选择哈希算法与哈希键类型。

哈希冲突的根源：哈希函数决定键值分布

在前面两节中，我们分别介绍了哈希表的原理与冲突处理方法——链式地址法（Chaining）与开放寻址法（Open Addressing）。需要特别强调的是：这两种方法都只是在冲突发生后让哈希表"还能正常工作"，并不能降低冲突发生的概率本身。相关实现可参考 链式地址哈希表（Python） 与 开放寻址哈希表（Python）。

如果哈希冲突过于频繁，哈希表的性能会急剧恶化。下图对比了链式地址法下哈希表的两种极端情况：理想情况下键值对均匀分布在各个桶（Bucket）中，查找效率最优；最坏情况下所有键值对都堆积在同一个桶中形成长链表，查找的时间复杂度退化为 $O(n)$。

那么，是什么决定了键值对的分布呢？答案是哈希函数。回顾哈希表计算桶索引的过程，需要先计算哈希值，再对数组长度取模：

index = hash(key) % capacity

从这条公式可以看出：当哈希表容量capacity固定时，真正决定输出结果的是哈希算法hash()本身，因此键值对在哈希表中的分布也由它决定。这意味着，要想减少哈希冲突，就应该把注意力集中在设计更好的哈希算法hash()上。

哈希算法的目标：快、稳、均匀

要让哈希表既快又可靠，哈希算法需要具备以下三个基本性质：

• 确定性（Determinism）：对于相同的输入，哈希算法必须始终输出相同的结果。只有这样才能保证哈希表行为的可复现与可靠。
• 高效性（Efficiency）：哈希值的计算必须足够快，计算开销越小，哈希表的实用价值越高。
• 均匀分布（Uniform Distribution）：哈希算法应尽量让键值对在哈希表中均匀分布。分布越均匀，哈希冲突的概率越低。

哈希算法的更多应用场景

在实践中，哈希算法的应用远不止哈希表，还包括：

• 密码存储：系统通常不直接保存用户明文密码，而是保存其哈希值。用户输入密码后，系统计算输入值的哈希并与存储值比对，一致则判定密码正确。
• 数据完整性校验：发送方计算数据的哈希值并随数据一同发出；接收方重新计算并比对，若一致则认为数据在传输过程中未被篡改。

密码学场景下的安全属性

对于涉及密码学安全的应用，为了防止通过哈希值反推原始密码等逆向分析行为，哈希算法还需要满足更严格的安全性质：

• 单向性（One-way）：仅凭哈希值无法还原出输入数据的任何信息。
• 抗碰撞性（Collision Resistance）：极难找到两个不同输入却拥有相同哈希值。
• 雪崩效应（Avalanche Effect）：输入数据的微小变化，应导致输出结果发生明显且不可预测的改变。

这里需要特别澄清一个常见误区："均匀分布"与"抗碰撞性"是两个相互独立的概念，满足前者并不意味着自动满足后者。例如，对于随机分布的输入key，key % 100可能产生足够均匀的分布；但这个算法过于简单——所有末两位相同的key都会得到相同结果，攻击者可以据此轻易构造出碰撞的key，例如用于破解密码。

设计简单的哈希算法

设计哈希算法是一项需要考虑诸多因素的复杂工程，但在一些对安全性要求不高的场景下，可以设计出以下几种简单实用的哈希算法：

• 加法哈希（Additive Hash）：将输入字符串所有字符的 ASCII 码相加，以总和作为哈希值。
• 乘法哈希（Multiplicative Hash）：利用乘法的"不相关性"，每一步都将当前值乘以一个常数，再加上当前字符的 ASCII 码。
• 异或哈希（XOR Hash）：通过异或运算把输入数据的各个元素逐步累积到一个哈希值中。
• 旋转哈希（Rotational Hash）：逐个累积字符的 ASCII 码，但每次累积前先对哈希值做循环移位。

在仓库中，这四个算法都有完整的跨语言实现，例如 simple_hash.py（Python） 和 simple_hash.c（C）。以 Python 实现为例，其核心代码如下：

def add_hash(key: str) -> int: """加法哈希""" hash = 0 modulus = 1000000007 for c in key: hash += ord(c) return hash % modulus def mul_hash(key: str) -> int: """乘法哈希""" hash = 0 modulus = 1000000007 for c in key: hash = 31 * hash + ord(c) return hash % modulus def xor_hash(key: str) -> int: """异或哈希""" hash = 0 modulus = 1000000007 for c in key: hash ^= ord(c) return hash % modulus def rot_hash(key: str) -> int: """旋转哈希""" hash = 0 modulus = 1000000007 for c in key: hash = (hash << 4) ^ (hash >> 28) ^ ord(c) return hash % modulus

观察这四种实现可以发现一个共同点：最后一步都是对一个大质数 $1000000007$ 取模，以保证哈希值保持在合理范围内、避免溢出。那么问题来了：为什么强调取模的模数要选质数？使用合数作为模数会有什么缺陷？这是一个非常值得深入思考的问题。

为什么取模要用大质数

先给出结论：使用大质数作为模数，能在最大程度上保证哈希值的均匀分布。因为质数与其他数没有公因数，这有助于削弱取余运算中产生的周期性规律，从而降低哈希冲突的发生频率。

不妨用一个具体例子来验证。假设我们选择合数 $9$ 作为模数，由于 $9$ 可以被 $3$ 整除，所有能被 $3$ 整除的key只会被映射到 $0$、$3$、$6$ 三个哈希值上：

$$ \begin{aligned} \text{modulus} & = 9 \newline \text{key} & = { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, \dots } \newline \text{hash} & = { 0, 3, 6, 0, 3, 6, 0, 3, 6, 0, 3, 6,\dots } \end{aligned} $$

如果输入key恰好符合这种等差数列分布，哈希值就会开始聚集，从而加剧哈希冲突。现在把模数换成质数 $13$，由于key与modulus之间没有公因数，哈希值分布的均匀性会显著改善：

$$ \begin{aligned} \text{modulus} & = 13 \newline \text{key} & = { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, \dots } \newline \text{hash} & = { 0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, \dots } \end{aligned} $$

需要说明的是：如果能够保证key本身是随机且均匀分布的，那么模数选质数还是合数区别并不大，两种都能得到均匀分布；但一旦key的分布存在周期性，取模合数就更容易导致聚簇（Clustering）。因此，实践中我们通常选择质数作为模数，并且这个质数宜大不宜小，以尽可能消除周期性规律、提高哈希算法的稳健性。这也是上面四个简单哈希算法统一采用 $1000000007$（即 $10^9+7$）的原因。

主流哈希算法对比：MD5 与 SHA 家族

需要承认的是，上述简单哈希算法都比较"脆弱"，与前面设定的目标相去甚远。例如，加法和异或满足交换律，因此加法哈希和异或哈希无法区分由相同字符构成但排列顺序不同的字符串，这既会加剧哈希冲突，也可能带来安全隐患。

在实践中，我们通常使用 MD5、SHA-1、SHA-2、SHA-3 等标准哈希算法，它们能够将任意长度的输入映射为固定长度的哈希值。近百年来，哈希算法持续演进：一部分研究者致力于提升性能，另一部分研究者与黑客则专注于寻找其安全漏洞。下表汇总了实际应用中常见的几种哈希算法：

对各算法的选型建议如下：

• MD5 与 SHA-1：已被多次成功攻击，在绝大多数需要安全性的场景中已被淘汰。
• SHA-256（SHA-2 家族）：目前最可靠的哈希算法之一，至今未出现已知的实际攻击手段，被广泛应用于各类协议与安全系统。
• SHA-3：相比 SHA-2 实现开销更小、计算效率更高，但目前普及程度仍不及 SHA-2 家族。

数据结构的内置哈希值

哈希表的key可以是整数、浮点数、字符串等多种数据类型。编程语言通常为这些类型提供内置的哈希算法，用于计算其在哈希表中的桶索引。以 Python 为例，可以调用内置函数hash()计算各种数据类型的哈希值（完整可运行示例见 built_in_hash.py）：

• 整数与布尔值的哈希值等于其本身（布尔值True的哈希值为1）。
• 浮点数与字符串的哈希计算较为复杂，感兴趣的读者可以自行深入研究。
• 元组的哈希值通过对每个元素分别哈希后再合并得到。
• 对象的哈希值通常基于其内存地址构建；如果重写对象的__hash__方法，则可以实现基于内容的哈希计算。

num = 3 hash_num = hash(num) # 整数 3 的哈希值为 3 bol = True hash_bol = hash(bol) # 布尔值 True 的哈希值为 1 dec = 3.14159 hash_dec = hash(dec) # 浮点数 3.14159 的哈希值为 326484311674566659 str = "Hello 算法" hash_str = hash(str) # 字符串 "Hello 算法" 的哈希值为 4617003410720528961 tup = (12836, "小哈") hash_tup = hash(tup) # 元组 (12836, '小哈') 的哈希值为 1029005403108185979 obj = ListNode(0) hash_obj = hash(obj) # 节点对象 <ListNode object at 0x1058fd810> 的哈希值为 274267521

不同语言的内置哈希接口与结果差异很大，这里给出一个跨语言对照（完整代码见 built_in_hash.py 及仓库codes/*/chapter_hashing/built_in_hash.*下各语言对应文件）：

• C++：通过std::hash<T>()函数对象计算，hash<int>()(3)返回3；但 C++ 内置std::hash仅覆盖基础类型，数组和自定义对象通常需要自行实现哈希。
• Java：通过包装类型的静态方法计算，如Integer.hashCode(3)返回3、Boolean.hashCode(true)返回1231、Double.hashCode(3.14159)返回-1340954729；字符串与数组分别使用str.hashCode()与Arrays.hashCode(arr)。
• C#：通过GetHashCode()实例方法计算，整数3返回3，浮点数3.14159返回-1340954729。
• Swift：通过hashValue属性计算，如num.hashValue；注意 Swift 对同一值每次进程运行的哈希结果可能不同。
• Dart / Kotlin / Ruby：均提供hashCode（Kotlin）或hash（Ruby）接口，例如 Dart 中num.hashCode为34803，Ruby 中3.hash为-4385856518450339636。
• Rust：没有内置的hash()函数，需要通过DefaultHasher配合Hash、Hashertrait 手动完成哈希计算，例如num.hash(&mut num_hasher)后调用finish()获取结果。
• Go / JavaScript / TypeScript / C：语言本身不提供内置的哈希码（hash code）接口，需要借助标准库或自行实现。

!!! tip

不同编程语言对内置哈希值的定义和计算方式各不相同，运行同一程序在不同语言中得到的结果可能完全不同，跨语言移植时切勿假设哈希值一致。

为什么只有不可变对象能当 key

在许多编程语言中，哈希表的key只能使用不可变对象。例如，如果使用列表（动态数组）作为key，一旦列表内容被修改，其哈希值也会改变，导致我们再也无法在哈希表中找到原先存储的value。

那么，像链表节点这样的自定义对象，其字段明明是可变的，为什么仍然可以哈希？原因在于对象的哈希值通常基于内存地址构建：即使对象内容发生变化，其内存地址保持不变，因此哈希值也不会改变。

Python 的随机盐与 HashDoS 防护

细心的读者可能会发现，同一程序在不同终端运行时，输出的字符串哈希值并不相同。这是因为 Python 解释器每次启动时都会为字符串哈希函数注入一个随机的盐（Salt）。这一机制能有效抵御 HashDoS 攻击——攻击者通过构造大量哈希碰撞的输入来拖垮哈希表，而随机盐使攻击者无法在运行前预知哈希函数的内部行为，从而显著提升哈希算法的安全性。

总结

回到本仓库哈希章节的整体脉络：哈希表的可靠性由两个层次共同保障——哈希函数负责"减少冲突"，冲突处理策略（链式地址、开放寻址）负责"消化冲突"。本文聚焦前者，从哈希算法的三大目标出发，依次探讨了简单哈希的构造、取模大质数的数学原理、MD5 与 SHA 家族的选型，以及各语言内置哈希的差异。理解这些内容后，无论是设计自定义哈希函数、选择加密哈希算法，还是决定何种类型可以作为哈希键，你都能做出更有依据的工程决策。如需进一步了解冲突处理的具体实现，可继续阅读仓库中的 哈希冲突处理 与 哈希表基础。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo