《Hello 算法》字符串简单哈希精讲：加法、乘法、异或、旋转四种朴素哈希的 Python 实现与逐行可视化

本篇以 Hello 算法仓库中 simple_hash 可视化文档及其背后完整的 simple_hash.py 源码为主体，围绕"如何为字符串设计一个朴素但可解释的哈希函数"展开。你会逐行看懂 add（加法）、mul（乘法）、xor（异或）、rot（旋转）四种经典简单哈希的构造思路，理解它们为何统一以超大质数 1000000007 取模、各自有怎样的局限性，并拿到可直接运行复现的可视化方案，为后续阅读标准哈希算法与哈希碰撞专题打下基础。

一、从文档看定位：一个可运行、可可视化的哈希小例子

仓库中 codes/pythontutor/ 目录下的 Markdown 文件，是 Hello 算法配套的"PythonTutor 可视化"资源：每个文件把某段核心代码以链接形式内嵌，读者点击即可进入逐步执行的动画视图。关联文档（繁體）页脚还带有 [file]{simple_hash}-[class]{}-[func]{rot_hash} 的标注，说明这份代码被 哈希算法章节文档 以"插入 simple_hash.py 源码并高亮 rot_hash 函数"的方式引用，属于该章节讨论"哈希算法的设计"时使用的标准示例。

该文档内嵌的正是这份源码的完整 Python 实现，简体版位于 codes/python/chapter_hashing/simple_hash.py，繁体镜像位于 zh-hant/codes/python/chapter_hashing/simple_hash.py。它定义了四个函数：

• add_hash(key)：加法哈希；
• mul_hash(key)：乘法哈希；
• xor_hash(key)：异或哈希；
• rot_hash(key)：旋转哈希。

主程序以字符串 "Hello 演算法"（即简体版的 "Hello 算法"）为输入，依次调用四个函数并打印结果。在 Python 3 下运行当前仓库中的源码，可以得到如下确定性的输出（纯算术运算，不依赖进程随机种子）：

加法哈希值为 88468
乘法哈希值为 2416626
异或哈希值为 30772
旋转哈希值为 993485442

说明：该字符串在 Python 中由 9 个字符组成，其 Unicode 码点依次为 72, 101, 108, 108, 111, 32, 28436, 31639, 27861（前五个是 ASCII 的 H/e/l/l/o，第六个是空格，后三个是"算法"两个汉字的码点）。后面分析四个算法时都会用到这组数。

二、先厘清上下文：哈希函数决定键值对分布

在进入代码之前，需要明确这段代码在整个哈希章节中的位置。Hello 算法在 哈希算法章节文档 中首先指出：无论是开放寻址还是链式地址，只能保证哈希表在冲突时"能工作"，而无法减少冲突本身；冲突一旦过于频繁，链式哈希表的查询复杂度会从理想的近似 $O(1)$ 劣化到最差 $O(n)$。

而哈希表定位桶下标的关键一步是"先算哈希值，再对数组长度取模"：

index = hash(key) % capacity

当容量 capacity 固定时，分布是否均匀完全取决于 hash() 这个函数本身。simple_hash.py 里的四个函数，就是用最直观的方式回答"hash() 该怎么写"的入门答案：输入一个字符串，输出一个 0 到模数之间的整数。

三、逐行精读四种简单哈希的 Python 实现

下面这份代码与仓库源码完全一致，可直接保存运行。四个函数共享同一个骨架：用 ord(c) 取出每个字符的码点参与运算，循环扫描整个字符串，最后对质数 modulus = 1000000007 取模，把结果收敛到安全范围。

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


"""Driver Code"""
if __name__ == "__main__":
    key = "Hello 演算法"

    hash = add_hash(key)
    print(f"加法哈希值为 {hash}")

    hash = mul_hash(key)
    print(f"乘法哈希值为 {hash}")

    hash = xor_hash(key)
    print(f"异或哈希值为 {hash}")

    hash = rot_hash(key)
    print(f"旋转哈希值为 {hash}")

3.1 加法哈希 add_hash：把每个字符的码点直接累加

hash += ord(c)

这是最直觉的做法：逐字符把码点相加。对示例字符串：

72 + 101 + 108 + 108 + 111 + 32 + 28436 + 31639 + 27861 = 88468

因为总和 88468 小于模数 1000000007，取模后数值不变，与运行输出一致。其优点是极其简单、计算量最小；缺点也很明显——完全丢弃了字符的位置信息。例如 "abc" 与 "cba" 的码点总和相同，哈希值必然相同；同时相邻字符组合（如 "ab" 与 "ba"）也无法区分，容易在真实数据中制造聚集。

3.2 乘法哈希 mul_hash：滚动地让"位置"进入哈希

hash = 31 * hash + ord(c)

每遇到一个字符，先把上一轮的结果乘以常数 31，再加上当前字符的码点。从公式结构可以看出，这是把字符串看作一个"以 31 为底的多项式"逐项求值：越靠前的字符，被乘 31 的次数越多，对最终值的影响呈指数放大，于是字符出现的先后次序被编码进了结果——这是它与加法哈希最本质的区别。例如 "ab" 得到 31*97+98，而 "ba" 得到 31*98+97，两者不同。

对示例字符串运行后，哈希值由"88468 量级"跃升到 2416626，说明累加过程中数值发散更快。实现上要注意：中间 31 * hash 可能很大，Python 整数无位数上限所以安全；在 C 等定宽整数语言中则需防范溢出（见第五节）。

3.3 异或哈希 xor_hash：逐位异或，零碰撞直觉

hash ^= ord(c)

用按位异或 ^ 把每个字符的码点累积进结果。异或自带"信息混合"特性：某一位上奇数个 1 结果为 1、偶数个 1 结果为 0，因此不同字符组合更容易产生不同的位模式。示例字符串的逐位异或结果是 30772。

但异或运算满足交换律与结合律，所以与加法哈希类似，它同样无法区分字符顺序不同的字符串，例如 "abc" 与 "cba" 的异或结果完全一样。这类顺序无关性，在章节文档中被明确列为简单哈希"脆弱"的原因之一。

3.4 旋转哈希 rot_hash：用移位实现"循环旋转"

hash = (hash << 4) ^ (hash >> 28) ^ ord(c)

这是四种算法里最精巧的一个。观察 << 4 与 >> 28，两者合计 32 位，恰好把上一轮的哈希值左移 4 位后又把被顶出的高位补回低位——这正是一次 32 位字长的"循环左移 4 位"（4 + 28 = 32）。随后把旋转结果与当前字符码点异或。

这样一来，每个字符的影响会随轮次在 32 位宽度内持续"滚动"并参与异或混合，既引入了位置信息，又让旧字符的影响长期保留且不断与后续字符纠缠。示例字符串最终得到 993485442，数值明显比前三者更分散、更接近模数的量级。由于该函数在 哈希算法章节文档 的代码插入中被选为高亮示例，阅读时建议配合 PythonTutor 逐步观察 hash 每一轮取值的 32 位形态变化。

算法	核心运算	位置敏感	示例输出（"Hello 演算法"）
加法哈希	hash += ord(c)	否	88468
乘法哈希	hash = 31 * hash + ord(c)	是	2416626
异或哈希	hash ^= ord(c)	否	30772
旋转哈希	hash = (hash << 4) ^ (hash >> 28) ^ ord(c)	是	993485442

四、为什么统一用大质数 1000000007 取模

四个函数几乎长得一模一样，是因为它们最后都执行：

hash % modulus   # modulus = 1000000007

1000000007 是一个约 10 亿量级的大质数。章节文档对此给出了一个值得反复琢磨的结论：取模运算若使用合数，容易让结果产生周期性聚集；质数不与大多数输入存在公因数，可以最大化保证哈希值均匀分布。

文档用一个对比实验说明。设输入恰好是一组公差为 3 的等差数列 key = {0, 3, 6, 9, ..., 33}：

• 若 modulus = 9（合数，可被 3 整除），由于所有 key 都能被 3 整除，key % 9 的结果只会循环落在 {0, 3, 6} 三个值上，哈希值明显聚堆；
• 若 modulus = 13（质数，与 3 互质），key % 13 的结果变为 {0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7}，几乎铺满整个取值区间，均匀性显著提升。

由此可见，模数选质数主要是为了对抗"输入本身具有周期性"的现实数据。文档同时补充了边界情况：如果输入是理想均匀随机的，那么质数还是合数做模数结果差别不大；只有输入带某种规律（比如上面的等差数列）时，合数模数的聚集缺陷才会显现。因此工程惯例是选一个足够大的质数作为模数，把哈希值压进合适的输出范围（1000000007 也恰好略小于 32 位有符号整数上限，方便落地到多数语言），同时尽量消除周期模式。

五、跨语言对照：从 C 实现反推底层细节

同一份算法在仓库中还有 C 语言实现 codes/c/chapter_hashing/simple_hash.c。对照两个版本，可以更清楚地看到语言特性对哈希实现的影响：

1）中间计算防溢出。 C 版四个函数的局部变量都声明为 long long，且加/乘/旋转三种在循环体内就做 % MODULUS：

hash = (31 * hash + (unsigned char)key[i]) % MODULUS;

原因很直白：31 * hash + key[i] 很容易超出 32 位 int 的表示范围，必须先扩宽到 64 位并及早取模，把中间值压回模数以内；而 Python 整数无上限，所以 Python 版可以把取模统一放到循环结束后执行一次，代码更简洁。两者在数学语义上等价。

2）字符读取的符号问题。 C 版统一用 (unsigned char)key[i] 读取字符码点，避免 char 在部分平台上的符号扩展导致负数参与运算；Python 的 ord(c) 天然返回无符号码点，无需这一步。

3）异或哈希的收尾方式存在差异。 Python 的 xor_hash 与其余三个函数一样以 % modulus 收尾，而 C 版的 xorHash 最后一行写作 return hash & MODULUS;，收尾方式与取模并不相同。跨语言对照时建议以语义统一、直观的 Python 版本为准理解算法思想，语言具体实现细节可视为各自的工程取舍。

六、正视局限：简单哈希为何"脆弱"？

章节文档在介绍完这四个算法后紧接着给出评价：它们都比较"脆弱"，远未达到哈希算法的设计目标。可验证的缺陷至少包括：

• 顺序混淆：加法、异或都满足交换律，无法区分 "abc" 与 "cba"，可能加剧碰撞；
• 碰撞可控性差：输入范围略大后，四种算法的输出分布都难保证均匀，更不用说抗碰撞。

对照 哈希算法章节文档 中给出的设计目标，可以理解差距所在：作为哈希表底层的哈希函数，应当确定性强（相同输入恒有相同输出）、效率高（计算开销小）、分布均匀（减少冲突）；而一旦用于密码存储、数据完整性校验等场景，还需要单向性（无法由哈希值反推输入）、抗碰撞性（难以找到两个同哈希输入）与雪崩效应（输入微变导致输出剧变）。需要特别澄清的是，"均匀分布"与"抗碰撞"是两个独立概念——例如 key % 100 在随机输入下可以均匀分布，却极易被逆向，根本无法用于口令保护。

这也是为什么真实世界几乎不会直接使用上述朴素哈希，而是采用 MD5、SHA-1、SHA-2、SHA-3 等标准算法（Hello 算法在章节中附有各算法的推出时间、输出长度、冲突情况与安全等级的对照表，并提示 MD5、SHA-1 已被弃用，SHA-256 仍是主流安全选择）。简单哈希的价值在于教学：它们把"哈希到底在算什么、为什么取模、为什么有碰撞"用几十行代码讲透，是理解工业级哈希的必要阶梯。

七、动手运行与可视化建议

仓库是只读的，你可以用两种方式在本地复现这段代码：

方式一：直接运行源码。 在仓库根目录执行：

python3 codes/python/chapter_hashing/simple_hash.py

即可看到四种哈希值与上文一致；也可以把源码复制到自己的 Python 环境中，替换 key 的取值，观察输入微小变化时四个输出的变动幅度，直观体会"雪崩效应"为何重要。

方式二：跟随 PythonTutor 逐步可视化。 打开仓库内的 simple_hash 可视化文档，其中内嵌了指向 PythonTutor 在线执行器的链接，会以 Python 3.11 加载本节代码并停在 curInstr=6 的初始断点处。逐行点击"前进"，可以同步观察 hash 变量在四个函数中每一轮的取值变化——尤其推荐配合 rot_hash 观察循环移位带来的位级混合过程。这正是该文档存在的意义：把"一维的代码执行"变成"可见的内存状态推演"。

结语

从一行 hash += ord(c) 到大质数取模的均匀性论证，再到 C 与 Python 两种实现的取舍差异，simple_hash 这二十多行代码浓缩了哈希函数设计的全部核心命题：计算什么、如何混合、如何收敛、何处脆弱。读完本文再回到 哈希算法章节文档 与哈希冲突处理（hash_map_chaining.py、hash_map_open_addressing.py）等后续主题时，你就能带着"分布是否均匀、是否抗碰撞"的视角去评估每一种工程方案了。