哈希函数：让数据找到自己的“专属座位”

从图书馆的故事说起

想象你去图书馆借书，图书管理员会怎么处理？如果他只是把书按照书名第一个字的笔画数放上书架，那么所有“王”开头的书（《王小波全集》《王阳明传》《王者荣耀攻略》……）都会堆在一个架子上，你找书时还得一本本翻。但如果管理员根据书的类别、作者姓氏拼音、出版年份等多个信息生成一个编号，比如“I247.5/W124/2021”，那每本书都能在书架上拥有一个相对独特的位置，找起来快多了。

哈希函数（Hash Function）干的就是这样一件事：给任意数据（比如你的姓名、学号、游戏ID）算出一个数字“编号”，让这个编号尽可能地对应到一个数组的某个位置，就像给数据安排了专属座位。如果两个数据算出相同的编号，就叫“冲突”（像两个人抢同一个座位）。好的哈希函数能尽量减少冲突，让数据均匀分布。

哈希函数的四大目标

哈希函数的核心追求可以总结为四个词：确定、高效、均匀、雪崩。

确定性（Deterministic）：同一个键永远算出同一个值。比如你的学号“20240301”，不管算多少次，结果都必须是同一个数。这是哈希表工作的基础，否则存进去的数据就找不回来了。
高效性（Efficient）：计算要快。哈希函数会被哈希表频繁调用（每次插入、查找都要算一次），如果计算太慢（比如对一个大字符串做复杂的加密运算），哈希表反而会变慢。简单加减乘除和位运算是最理想的。
均匀性（Uniform）：不同的键尽量映射到不同的位置，且所有位置被占用的概率大致相等。就像分座位：如果全班40人，哈希表有40个位置，理想情况是每人一个位置，最多偶尔两三人冲突。但如果哈希函数有偏向性，比如只把数据分到前10个位置，后30个空着，那就成了“假哈希表”，性能退化到链表级别。
雪崩效应（Avalanche Effect）：输入微小的变化（比如把“hello”改成“hellp”），输出的哈希值应该完全不同，而不是只有最后一位不同。这样能避免规律性聚集。比如字符串哈希中，如果只靠第一个字做决定，那“hello”和“heavy”可能只差1，导致它们很容易冲突；而好的算法会让它们天上地下。

五种常见的哈希函数设计方法

1. 除法散列法（取模法）—— 简单但挑模数

公式：h(key) = key % M，M 是哈希表的大小。

核心秘密：M 最好选一个质数（比如 7、13、31、97），并且不要是 2 的幂（比如 8、16、32）。为什么？因为计算机里很多数据天然是 2 的倍数（比如地址、编号），如果 M 是 8，那么所有 key 的低 3 位决定了位置，高位的数字完全浪费了。比如 key 是 8、16、24、32……它们模 8 都等于 0，全部冲突！而质数能让高位和低位的信息都起作用，分布更均匀。

生活例子：运动会按班级号分列，班级号是 1~12。如果用班级号 % 4，那么 1、5、9 班都分到第一列，2、6、10 班分到第二列……这就是模数选 4 的问题。如果改为班级号 % 7（用 7 列），分布会均匀很多，因为 7 和 12 互质。

新手常犯错误：直接使用数组长度作为 M，比如数组长度是 100，就用 % 100。但 100 是合数，且是 2 和 5 的倍数，如果 key 多数是 10 的倍数（比如成绩、金额），会引发大量冲突。建议把表大小设为一个不太靠近 2 的幂的质数，比如 101、131、1009。

2. 乘法散列法 —— 不怕模数大小

公式：h(key) = floor( M * ( (key * A) % 1 ) )
其中 (key * A) % 1 表示取 key * A 的小数部分，A 是一个 0~1 之间的常数。常用黄金比例倒数 (√5 - 1)/2 ≈ 0.6180339887。

优点：M 可以选 2 的幂（比如 128、256），因为乘法后取小数部分再乘以 M，相当于取了高位的一些信息，不依赖 M 的奇偶性。计算机里 × M 用左移实现很快。

生活类比：切蛋糕时，你想均匀地切成 M 块，但每块大小不完全相等。乘法散列法相当于先让每块蛋糕的“剩余部分”乘一个无理数，再切，这样每块的大小比例被搅散，分布更均匀。

3. 字符串哈希 —— 把字符串当“多进制数”

字符串没法直接取模，但可以把它看作一个“多进制”的数。比如字符串 "abc" 的 ASCII 码分别是 97、98、99，我们可以像计算 31 进制数一样算出它的值：
hash = 97 * 31^2 + 98 * 31 + 99。

常用算法：BKDR 哈希
它用基数 seed（常用 31、131、137）累加每个字符：

hash = 0
for each char c:
    hash = hash * seed + (int)c

最后再取模。注意：如果哈希值会非常大，需要取一个大质数模数（比如 1e9+7）或者用无符号整数自动溢出（C++ 里 unsigned int 溢出相当于自动取模 2^32）。

为什么用 31 或 131？ 它们是质数，且不是太大，乘法时不容易溢出，同时能混合字符的先后顺序信息。31 还可以写成 31 = 32 - 1，编译器可以优化为移位和减法，效率高。

生活中的例子：假设你要给全班同学按名字分配储物柜。名字是字符串，你用一个哈希函数把名字转成数字，再对柜子总数取模。如果名字相似（比如“小明”和“小朋”只有最后一字不同），好的哈希函数应该让它们分到不同的柜子；如果用简单的“首字母取模”，那所有姓“王”的同学全撞一起——这就是坏哈希。

新手常犯错误：直接用字符 ASCII 码相加，比如 "ab" = 97+98=195，"ba" = 98+97=195 一样！这种“加法哈希”完全丢失了顺序信息，导致大量无意义冲突。必须用乘法保留顺序。

4. 折叠法 —— 把大数切成小段再混合

如果键是一个很长的数字（比如身份证号、电话号码），可以把它分成几段，然后相加、异或或做其他运算。

例子：电话号码 12345678

分两段：1234 + 5678 = 6912
再取模表大小（比如 100），得到 12。
你也可以交错：1234 XOR 5678，或加完再取中间几位。这个方法简单，但需要自己决定分段方式。

5. 平方取中法 —— 利用平方的中间位

先计算 key 的平方，然后取中间几位（位数根据表大小调整）。因为平方运算会让各位数字相互影响，中间位能混合高低位的信息。

例子：key=1234

平方 = 1522756
取中间三位：227（从第2位开始，取3位）。
如果表大小是 100，可以取中间两位。

这个方法适合键值不太大的整数，但计算平方在键很大时可能溢出，需要小心使用。

完整示例：用 BKDR 哈希给名字分配座位

我们写一个完整程序：有 10 个同学的名字，要分到 7 个座位（表大小 7，质数）。用 BKDR 哈希函数计算每个名字的座位号，并显示分布情况。

C++ 实现

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// BKDR 哈希函数：输入字符串和模数，返回 [0, mod-1] 范围的哈希值
unsigned int BKDRHash(const string& str, unsigned int mod) {
    unsigned int seed = 131; // 常用种子
    unsigned int hash_val = 0; // 哈希值，初始为0
    for (char ch : str) { // 遍历每个字符
        hash_val = hash_val * seed + (unsigned int)ch; // 累加
    }
    return hash_val % mod; // 取模返回
}

int main() {
    // 学生名字列表
    vector<string> names = {"张三", "李四", "王五", "赵六", "孙七", 
                            "周八", "吴九", "郑十", "钱十一", "陈十二"};
    int table_size = 7; // 哈希表大小（质数）
    
    cout << "姓名 -> 座位号" << endl;
    for (string name : names) {
        unsigned int seat = BKDRHash(name, table_size);
        cout << name << " -> " << seat << endl;
    }
    
    // 统计每个座位有多少人
    vector<int> count(table_size, 0);
    for (string name : names) {
        unsigned int seat = BKDRHash(name, table_size);
        count[seat]++;
    }
    cout << "\n座位分布：" << endl;
    for (int i = 0; i < table_size; i++) {
        cout << "座位" << i << ": " << count[i] << "人" << endl;
    }
    return 0;
}

可能的输出（由于字符串不同，实际运行结果可能不同，但分布应大致均匀）：

姓名 -> 座位号
张三 -> 5
李四 -> 2
王五 -> 0
赵六 -> 4
孙七 -> 1
周八 -> 6
吴九 -> 3
郑十 -> 2
钱十一 -> 0
陈十二 -> 5
座位0: 2人
座位1: 1人
座位2: 2人
座位3: 1人
座位4: 1人
座位5: 2人
座位6: 1人

可以看到，虽然有个别座位有 2 人（冲突），但整体比较均匀。如果换成“取首字母哈希”，估计“张三”和“周八”都姓“Z”（拼音首字母）会撞一起，结果就难看了。

Python 实现

def bkdr_hash(s: str, mod: int) -> int:
    """BKDR 哈希，返回 [0, mod-1] 的整数"""
    seed = 131
    hash_val = 0
    for ch in s:
        # Python 整数无溢出，但可以每次取模防止过大，不过取模太频繁会慢
        hash_val = hash_val * seed + ord(ch)
    return hash_val % mod

if __name__ == "__main__":
    names = ["张三", "李四", "王五", "赵六", "孙七",
             "周八", "吴九", "郑十", "钱十一", "陈十二"]
    table_size = 7
    print("姓名 -> 座位号")
    for name in names:
        seat = bkdr_hash(name, table_size)
        print(f"{name} -> {seat}")
    
    # 统计分布
    count = [0] * table_size
    for name in names:
        seat = bkdr_hash(name, table_size)
        count[seat] += 1
    print("\n座位分布：")
    for i, cnt in enumerate(count):
        print(f"座位{i}: {cnt}人")

如何评价一个哈希函数好不好？

我们可以用两个简单指标：

冲突数量：在相同的键集合下，冲突越少越好。最好让大部分键都独享一个位置，冲突的键数不超过总数的 10%~20%。
分布均匀度：计算每个位置上的键数量的方差或标准差。如果某几个位置空着，某几个位置挤满了人，说明哈希函数有偏向。理想情况下，每个位置的负载应该接近 键总数 / 表大小。

注意：哈希函数的好坏还依赖于你的数据特点。比如除法散列法对整数键有效，但对连续的电话号码可能不好（电话号码后几位变化大，前几位重复多，取模时应该考虑）。BKDR 对字符串普遍有效，但如果键是固定长度的数字串，可能平方取中法更合适。

新手最容易掉进的三个坑

坑1：用加法哈希处理字符串

错误做法：

int bad_hash(string s) {
    int sum = 0;
    for (char c : s) sum += c;
    return sum % M;
}

这样“ab”和“ba”结果相同，顺序丢失，大量冲突。必须用乘法保留顺序。

坑2：取模时 M 选 2 的幂

比如 M = 256，直接 key % 256 只用了 key 的最低 8 位，高位信息全部丢弃。如果 key 是 0, 256, 512, 768……全部冲突。除非使用乘法散列法，否则 M 不要选 2 的幂。

坑3：选择非质数的模数

合成数（如 100、200）往往有因子，如果 key 本身是这些因子的倍数，就会产生规律性冲突。比如 M=100，所有 key 是 10 的倍数都会落到 0,10,20,…这些位置。尽量选质数，如 101、1009、10007。

总结与下一步

哈希函数是哈希表的灵魂。一个好的哈希函数能让你的程序像图书馆的好管理员一样，迅速找到每本书的位置；一个坏的哈希函数则会让哈希表退化成链表的效率（全塞一个桶里）。我们学习了：

四大目标：确定、高效、均匀、雪崩
五种方法：除法、乘法、字符串（BKDR）、折叠、平方取中
实用技巧：模数选质数、字符串哈希用 131 或 31 基数

但即使最好的哈希函数，也难免遇到冲突（比如恰好两个不同的字符串算出相同结果）。这时候该怎么办？别担心，下一课我们将学习 冲突处理方法——当数据抢同一个座位时，怎么优雅地安排它们（比如链地址法、开放地址法）。熟悉了这些，你就能亲手实现一个完整的哈希表了！

相关知识点：

哈希函数的设计