Hello 算法：四种简易哈希算法的设计原理与 Python 实现（附逐步可视化）

本篇基于《Hello 算法》仓库中的可视化文件 simple_hash.md 展开，聚焦哈希算法这一数据结构的核心环节：如何通过 add_hash、mul_hash、xor_hash、rot_hash 四种简易算法把任意字符串映射为哈希值，以及为什么最后一步要对大素数 1000000007 取模。读完本文，你将掌握这四种算法的完整 Python 实现、各自的弱点（如加法与 XOR 的可交换性缺陷），并能结合仓库源码理解“哈希函数决定冲突概率”这一哈希表性能的关键命题。

哈希算法在哈希表中的位置

在哈希表中，键值对的桶下标由两步决定：

index = hash(key) % capacity

当容量 capacity 固定时，index 的分布完全由哈希算法 hash() 的输出决定。正如 hash_algorithm.md 所论述的：开放寻址法和链地址法只是让哈希表在冲突发生时能"正确工作"，但并不降低冲突发生的概率——键值对均匀散列到所有桶时查找效率最优，而所有键值对挤进同一个桶时，时间复杂度会退化为 O(n)。因此，冲突过多时性能下降的根源往往不在冲突解决策略，而在哈希函数本身。

一个合格的哈希算法需要同时满足三个目标：

• 确定性：相同输入永远产生相同输出，否则哈希表无法可靠找回数据；
• 高效率：哈希值计算必须足够快，计算成本越低，哈希表的实际价值越高；
• 均匀分布：键值对在表中的分布越均匀，哈希冲突的概率就越低。

对于密码学场景，还额外要求单向性（无法由哈希值反推输入）、抗碰撞性（极难找到两个不同输入产生同一哈希值）和雪崩效应（输入的微小变化导致输出的剧烈、不可预测变化）。值得注意的是，"均匀分布"与"抗碰撞性"是两个独立概念：例如 key % 100 对随机输入也能给出较均匀的分布，但由于它过于简单，所有末两位相同的 key 必然碰撞，且能轻易由哈希值反推构造出碰撞输入，存在安全隐患。

四种简易哈希算法的完整实现

仓库中对应的可运行源码为 simple_hash.py，与 pythontutor 可视化文件 simple_hash.md 中的代码逐行一致。四个函数结构相同：逐字符遍历输入字符串 key，将 ASCII 码（ord(c)）累积进 hash，最后对 modulus = 1000000007 取模返回。

1. 加法哈希（add_hash）

def add_hash(key: str) -> int:
    """加法哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash += ord(c)
    return hash % modulus

将所有字符的 ASCII 码相加，把总和作为哈希值。实现最简单，但它有两个明显缺陷：

• 可交换性：加法满足交换律，因此 add_hash("ab") == add_hash("ba")，任何仅字符顺序不同、字符构成相同的字符串都会碰撞；
• 只与长度和字符组成相关：输入越长哈希值越大，长字符串天然倾向更大的桶区间，分布不均。

2. 乘法哈希（mul_hash）

def mul_hash(key: str) -> int:
    """乘法哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash = 31 * hash + ord(c)
    return hash % modulus

每一步先把当前哈希值乘以常数 31，再加上下一个字符的 ASCII 码。乘法打破了加法顺序无关的特性：同一个字符在不同位置产生的贡献是 31^k 倍关系（k 为位置权重），因此 mul_hash("ab") != mul_hash("ba")。31 是 Java String.hashCode() 的经典选择，它既是奇数素数，又便于 JVM 优化（31 * hash 可被编译为 hash << 5 - hash）。

3. XOR 哈希（xor_hash）

def xor_hash(key: str) -> int:
    """XOR 哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash ^= ord(c)
    return hash % modulus

利用位运算 XOR（^）将字符 ASCII 码依次异或累积。XOR 同样满足交换律，因此和加法哈希一样区分不了字符顺序；此外，若字符串中某字符出现偶数次，它会被完全"抵消"，进一步加剧碰撞。

4. 移位旋转哈希（rot_hash）

def rot_hash(key: str) -> int:
    """移位旋转哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash = (hash << 4) ^ (hash >> 28) ^ ord(c)
    return hash % modulus

在累积每个字符前，先将哈希值做循环左移：(hash << 4) ^ (hash >> 28) 等价于把 32 位无符号整数整体左移 4 位——低 4 位移出的部分通过右移 28 位被"绕"回高位。这样每一位字符的影响都能随着轮次扩散到整个字面，初步具备雪崩效应的雏形，同时仍保持 O(n) 的线性计算成本。

运行结果与顺序敏感性验证

以仓库 Driver Code 中的 key = "Hello Algo" 为例，四个算法的实际输出为（与 simple_hash.py 运行结果一致）：

算法	哈希值（对 1000000007 取模）	对 "Algo Hello" 的哈希是否相同
add_hash	919	相同（加法可交换）
mul_hash	198553274	不同（位置敏感）
xor_hash	71	相同（XOR 可交换）
rot_hash	870102307	不同（位置敏感）

上表同时验证了文档的论断：加法哈希与 XOR 哈希因满足交换律，无法区分"组成相同但顺序不同"的字符串，这会放大哈希冲突，甚至带来安全隐患；乘法与移位旋转哈希则因位置加权而区分了顺序。

为什么取模使用大素数 1000000007

四种算法的收尾都是 hash % 1000000007，目的不仅是把哈希值限制在合理范围内，更在于取模运算本身的性质会影响分布均匀性。hash_algorithm.md 中给出了一个直观反例：若取合数 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, ... }

换成素数 13 后，同一组 key 的哈希值变为 0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, ...，分布明显更均匀。原因是素数与任何其他整数都没有公因子，能最大程度打散取模运算产生的周期性规律；而合数模下，凡是与模存在公因子的输入序列都会形成"算术级数 → 哈希值聚集"的坏模式。因此实践中的通用做法是：选一个足够大的素数作模数——大，是为了消除周期规律；素数，是为了抗聚集。需要说明的是，若能保证 key 本身是随机均匀分布的，合数与素数模差别不大；风险主要集中在 key 带有周期性的场景（如自增 ID、规律性编码）。

简易算法的局限与工程选型

仓库文档总结的结论是：上述四种简易算法"相当脆弱"，只适合教学和无对抗场景。真实系统中通常采用标准哈希算法，它们能把任意长度的输入映射到固定长度的哈希值：

	MD5	SHA-1	SHA-2	SHA-3
出现年份	1992	1995	2001	2008
输出长度	128 bit	160 bit	256/512 bit	224/256/384/512 bit
碰撞风险	频繁	频繁	罕见	罕见
安全性	低，已被攻破	低，已被攻破	高	高
应用	已弃用，仍用于数据完整性校验	已弃用	加密货币交易校验、数字签名等	可作为 SHA-2 的替代

此外，哈希算法的用途并不限于哈希表：系统通常存储密码的哈希值而非明文，通过重新计算比对完成验证；发送方可随数据附带哈希值，接收方重新计算即可校验数据完整性。

与仓库中哈希表实现的联动

理解简易哈希算法后，可以再看仓库中它的"消费方"：

• hash_map_chaining.py：链地址法哈希表，hash_func 目前是 key % capacity，其中 key 为整数。若将 capacity 换成素数（如 13 而非 12），可以立即用上本文讨论的素数模抗聚集原理；
• hash_map_open_addressing.py：开放寻址法哈希表，冲突解决策略与哈希函数质量是两条正交的优化线；
• built_in_hash.py：演示 Python 内置 hash() 在不同类型上的行为——整数哈希值等于其本身、布尔 True 为 1、字符串与浮点数有各自算法、对象默认基于内存地址。这也解释了为什么哈希表通常只允许不可变对象作键：若键的内容可变，其哈希值改变后将无法在表中定位原桶，破坏查找的确定性这一哈希算法的第一目标。

pythontutor 可视化文件 simple_hash.md 正是 hash_algorithm.md 中 [file]{simple_hash} 代码块对应的逐步执行视图，读者可沿"哈希函数 → 冲突解决 → 哈希表整体"这条线索，在仓库的 ru/docs/chapter_hashing/ 目录下继续阅读 hash_map.md、hash_collision.md 等文档，形成完整的哈希章节知识链。