Hello 算法:哈希算法的设计与实现——从简单哈希函数到主流语言内置哈希值

2026-09-06 14:57:45作者：史锋燃Gardner

哈希算法决定了键值对在哈希表中的分布质量，是降低哈希冲突、保证哈希表高性能的核心环节。本文基于《Hello 算法》仓库中哈希算法一章展开，系统讲解哈希算法的设计目标、四类简单哈希算法的源码级实现、为什么取模要选大质数，以及 MD5/SHA 系列等常见标准哈希算法与各大语言内置哈希机制的差异，读完可掌握"既快又稳"的哈希函数设计原则及在 Python、C++、Java 等语言中计算内置哈希值的方法。

为什么哈希冲突的治理要聚焦哈希算法

在哈希表一节中介绍的开放寻址与链地址法，只能保证哈希表在发生冲突时正常工作，而无法减少冲突本身的发生。如果哈希冲突过于频繁，哈希表性能会急剧劣化。如下图所示，链地址哈希表在理想情况下键值对均匀分布在各个桶中，查询效率最佳；最差情况下所有键值对都落入同一个桶，时间复杂度退化至 $O (n)$ 。

键值对的分布情况由哈希函数决定。回忆哈希函数把键映射到桶索引的计算步骤——先计算哈希值，再对数组长度取模：

index = hash(key) % capacity

当哈希表容量 capacity 固定时，哈希算法 hash() 直接决定了输出值，进而决定了键值对在表中的分布。因此，要降低冲突概率，注意力必须集中在 hash() 本身的设计上，而不是只依赖冲突解决策略。

哈希算法的设计目标

为了实现"既快又稳"的哈希表数据结构，哈希算法应具备三个基本特点：

确定性：对于相同的输入，始终产生相同的输出，这样才能确保哈希表是可靠的；
效率高：计算哈希值的过程应足够快，计算开销越小，哈希表的实用性越高；
均匀分布：哈希算法应使键值对均匀分布在哈希表中，分布越均匀，冲突概率越低。

哈希算法的用途远不止哈希表，还广泛应用于其他领域：

密码存储：系统通常不直接存储明文密码，而是存储密码的哈希值；用户登录时对新输入的密码计算哈希，与存储值比对，匹配即视为密码正确；
数据完整性检查：发送方将数据的哈希值随数据一同发送，接收方重新计算并比对，匹配则数据完整。

对于密码学相关应用，为了防止从哈希值反推原始数据等逆向工程，哈希算法还需要更高等级的安全特性：

单向性：无法通过哈希值反推出关于输入数据的任何信息；
抗碰撞性：极难找到两个不同的输入，使得它们的哈希值相同；
雪崩效应：输入的微小变化应当导致输出的显著且不可预测的变化。

需要特别强调："均匀分布"与"抗碰撞性"是两个独立的概念，满足均匀分布不一定满足抗碰撞性。例如在随机输入 key 下，哈希函数 key % 100 可以产生均匀分布的输出；然而该算法过于简单，所有后两位相等的 key 输出都相同，攻击者可以很容易地从哈希值反推出可用的 key，从而破解密码。

四类简单哈希算法的源码解析

哈希算法的设计是一个需要考虑许多因素的复杂问题，但在要求不高的场景下，可以设计一些简单哈希算法。哈希算法一章给出了四类经典实现，仓库中在 codes/python/chapter_hashing/simple_hash.py 提供了完整可运行代码，C++ 与 C 版本分别见 codes/cpp/chapter_hashing/simple_hash.cpp 和 codes/c/chapter_hashing/simple_hash.c：

"""
File: simple_hash.py
Created Time: 2023-06-15
Author: krahets (krahets@163.com)
"""


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

四类算法的核心思想：

加法哈希：对输入的每个字符的 ASCII 码进行相加，将总和作为哈希值；
乘法哈希：利用乘法的不相关性，每轮乘以一个常数（此处为 31），将各字符的 ASCII 码累积到哈希值中；
异或哈希：将每个元素通过异或操作累积到一个哈希值中；
旋转哈希：每累积一个字符前，先对哈希值做"左移 4 位再与右移 28 位结果异或"的旋转操作（hash = (hash << 4) ^ (hash >> 28) ^ ord(c)），使高位信息向低位扩散。

为什么最后一步要对大质数取模

观察源码可以发现，每种哈希算法的最后一步都是对大质数 1000000007 取模，以确保哈希值在合适范围内。值得思考的是：为什么要强调对质数取模，对合数取模的弊端是什么？

结论是：使用大质数作为模数，可以最大化地保证哈希值的均匀分布。因为质数不与其他数字存在公约数，可以减少因取模操作而产生的周期性模式，从而避免哈希冲突。

举个直观例子，假设选择合数 9 作为模数，它可以被 3 整除，那么所有能被 3 整除的 key 都会被映射到 0、3、6 这三个哈希值上：

modulus = 9
key     = { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, ... }
hash    = { 0, 3, 6, 0, 3, 6, 0, 3, 6, 0, 3, 6, ... }

如果输入 key 恰好满足这种等差数列的数据分布，哈希值就会出现"聚堆"，从而加重哈希冲突。现在将 modulus 替换为质数 13，由于 key 与 modulus 之间不存在公约数，输出哈希值的均匀性明显提升：

modulus = 13
key     = { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, ... }
hash    = { 0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, ... }

值得说明的是，如果能保证 key 本身随机均匀分布，那么选质数或合数作为模数都能输出均匀分布的哈希值；而当 key 的分布存在某种周期性时，对合数取模更容易出现聚集现象。总而言之，通常选取质数作为模数，且这个质数最好足够大，以尽可能消除周期性模式，提升哈希算法的稳健性。

常见标准哈希算法：MD5、SHA-1、SHA-2、SHA-3

不难发现，上述简单哈希算法都比较"脆弱"，远未达到哈希算法的设计目标。例如由于加法和异或满足交换律，加法哈希和异或哈希无法区分内容相同但顺序不同的字符串，这可能会加剧哈希冲突并引起安全问题。

实际工程中通常采用标准哈希算法，例如 MD5、SHA-1、SHA-2 和 SHA-3，它们能将任意长度的输入数据映射到恒定长度的哈希值。近一个世纪以来，哈希算法处于不断升级与优化的过程中：一方面研究人员努力提升性能，另一方面另一部分研究人员和黑客致力于寻找其安全问题。实际应用中常见哈希算法的对比如下：

	MD5	SHA-1	SHA-2	SHA-3
推出时间	1992	1995	2002	2008
输出长度	128 bit	160 bit	256/512 bit	224/256/384/512 bit
哈希冲突	较多	较多	很少	很少
安全等级	低，已被成功攻击	低，已被成功攻击	高	高
应用	已被弃用，仍用于数据完整性检查	已被弃用	加密货币交易验证、数字签名等	可用于替代 SHA-2

MD5 和 SHA-1 已多次被成功攻击，被各类安全应用弃用；
SHA-2 系列中的 SHA-256 是最安全的哈希算法之一，仍未出现成功的攻击案例，常用在各类安全应用与协议中；
SHA-3 相较 SHA-2 的实现开销更低、计算效率更高，但目前使用覆盖度不如 SHA-2 系列。

主流语言的内置哈希值：机制与差异

哈希表的 key 可以是整数、小数或字符串等数据类型，编程语言通常会为这些类型提供内置哈希算法，用于计算哈希表中的桶索引。以 Python 为例，可以调用 hash() 函数计算各种数据类型的哈希值（仓库中对应示例见 codes/python/chapter_hashing/built_in_hash.py）：

整数和布尔量的哈希值就是其本身；
浮点数和字符串的哈希值计算较为复杂；
元组的哈希值是对其中每个元素进行哈希，再将这些哈希值组合成单一哈希值；
对象的哈希值基于其内存地址生成，通过重写对象的哈希方法可实现基于内容生成哈希值。

Python：`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

C++：`std::hash` 仅覆盖基本类型

int num = 3;
size_t hashNum = hash<int>()(num);
// 整数 3 的哈希值为 3

bool bol = true;
size_t hashBol = hash<bool>()(bol);
// 布尔量 1 的哈希值为 1

double dec = 3.14159;
size_t hashDec = hash<double>()(dec);
// 小数 3.14159 的哈希值为 4614256650576692846

string str = "Hello 算法";
size_t hashStr = hash<string>()(str);
// 字符串"Hello 算法"的哈希值为 15466937326284535026

从源码结构看，C++ 内置 std::hash 仅提供基本数据类型的哈希值计算，数组、对象的哈希值需要自行实现（这一点在 codes/cpp/chapter_hashing/built_in_hash.cpp 示例中也有体现）。

Java / C# / Kotlin：`hashCode()` 体系

Java 通过包装类的静态方法与对象方法计算哈希，例如 Integer.hashCode(num)、Boolean.hashCode(bol)、Double.hashCode(dec)、str.hashCode()，数组可用 Arrays.hashCode(arr)；对象 obj.hashCode() 基于内存地址。C# 与 Kotlin 语法类似，直接调用 num.GetHashCode() / num.hashCode()，Boolean.hashCode 固定为 1231。各语言对同一数值给出的哈希值往往不同（例如 Dart 中整数 3 的 hashCode 是 34803，Swift 的 hashValue 是一个大整数），不同编程语言的内置哈希值计算函数的定义和方法各不相同，跨语言不可直接比对。

此外，Go、JavaScript、TypeScript、C 等语言未提供内置 hash code 函数，需要自行实现或借助标准库的哈希工具。

哈希键的不可变性与字符串哈希加盐

在许多编程语言中，只有不可变对象才可作为哈希表的 key。假如将列表（动态数组）作为 key，当列表内容发生变化时，其哈希值随之改变，我们就无法在哈希表中查询到原先的 value 了。

虽然自定义对象（比如链表节点）的成员变量是可变的，但它依然是可哈希的。这是因为对象的哈希值通常基于内存地址生成，即使对象内容变化，内存地址不变，哈希值仍然不变。

细心的读者可能发现，在不同控制台中运行程序时，字符串输出的哈希值是不同的。这是因为 Python 解释器在每次启动时，都会为字符串哈希函数加入一个随机的盐（salt）值。这种做法可以有效防止 HashDoS 攻击——攻击者若无法预先知道盐值，就难以构造大量哈希冲突的输入对服务器发起拒绝服务攻击，从而提升哈希算法的安全性。