10. 字符串哈希：从需求到实现

字符串哈希，说白了就是把一个字符串映射成一个整数。你可能会问：好好的字符串，干嘛非要转成数字？

我刚开始学哈希表的时候也有这个疑问。后来在做一个关键词过滤系统时，发现用字符串直接做查找，效率低得让人抓狂。每次比较都要逐字符比对，数据量一上来，CPU 都在哀嚎。这时候我才意识到——字符串哈希，是解决这个问题的关键。

为什么需要字符串哈希？

哈希表的核心是「键到索引的映射」。如果键是整数，直接取模就行。但现实世界中的键，大多是字符串——用户名、URL、IP 地址、文件路径……

你想想看，如果哈希表直接拿字符串当键，每次查找都要做字符串比较。两个字符串哪怕只差一个字符，也得从头比到尾。这效率，能忍？

字符串哈希的作用，就是把任意长度的字符串，压缩成一个固定长度的整数。然后这个整数就可以作为哈希表的键，或者直接用来计算桶索引。

三种经典的字符串哈希算法

我这些年用过的字符串哈希算法不下十种，但真正经得起考验的，也就那么几个。下面这三个是我个人最常用的，也是工业界公认的经典。

BKDR 哈希

BKDR 哈希的思路很简单：把字符串当成一个「以某个基数为底的数值」。比如字符串 "abc"，可以看成是 a * 131^2 + b * 131 + c。这个 131 就是种子（seed）。

为什么选 131？嗯，这是个经验值。我试过 31、131、1313，发现 131 在大多数场景下碰撞率最低。当然，你也可以用 31，效果也不错。

unsigned long BKDRHash(const char *str) {
    unsigned long hash = 0;
    unsigned long seed = 131; // 31, 131, 1313 都可以
    while (*str) {
        hash = hash * seed + (*str++);
    }
    return hash;
}

这段代码看起来简单，但有个细节要注意：hash * seed 可能会溢出。不过没关系，C 语言的无符号整数溢出是定义良好的行为，相当于自动取模 2^32。这反而帮我们做了哈希值的范围控制。

DJB 哈希

DJB 哈希是 Daniel J. Bernstein 设计的。它的核心思想是：每次迭代都让哈希值乘以 33，然后加上当前字符的 ASCII 码。

unsigned long DJBHash(const char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}

注意看这行：(hash << 5) + hash。左移 5 位相当于乘以 32，再加一次自身，就是乘以 33。这种写法比直接写 hash * 33 快一点——虽然现代编译器会帮你优化，但写出来更显功力。

为什么初始值是 5381？我记得 DJB 本人说过，这个数字的二进制形式「看起来比较随机」。嗯，有时候算法设计就是这么玄学。

FNV 哈希

FNV 哈希的全称是 Fowler–Noll–Vo 哈希。它有两种变体：FNV-1 和 FNV-1a。区别在于，FNV-1 先乘后异或，FNV-1a 先异或后乘。

// FNV-1a 版本（推荐）
unsigned long FNV1aHash(const char *str) {
    unsigned long hash = 2166136261UL;
    while (*str) {
        hash ^= (unsigned char)(*str++);
        hash *= 16777619UL;
    }
    return hash;
}

FNV 哈希的种子和乘数都是精心挑选的质数。2166136261 和 16777619，这两个数字看起来随意，但经过大量测试，它们能让哈希值分布得特别均匀。

我曾经在日志分析系统中对比过这三种算法。处理 100 万条 URL 时，FNV-1a 的碰撞率最低，只有 BKDR 的 60% 左右。但 BKDR 的计算速度更快，比 FNV 快大约 15%。

算法	速度（相对）	碰撞率（相对）	推荐场景
BKDR	快	中等	中长字符串、通用场景
DJB	很快	较低	短字符串、命令键
FNV-1a	中等	很低	对碰撞敏感的场景

字符串哈希的碰撞问题

说白了，哈希碰撞是躲不开的。因为哈希值空间有限（比如 32 位整数只有 4G 个可能值），而字符串的数量是无限的。根据鸽巢原理，碰撞必然存在。

但真正让我头疼的，不是理论上的碰撞，而是实际中的「恶意碰撞」。我在做 Web 防火墙时遇到过一种攻击：攻击者故意构造大量哈希值相同的字符串，让哈希表退化成链表，导致服务器 CPU 飙升到 100%。

处理碰撞的常见策略有几种：

• 链地址法：每个桶里挂一个链表。简单，但链表太长时性能下降。
• 开放地址法：碰撞了就往下一个空位放。适合数据量不大的场景。
• 双重哈希：用两个不同的哈希函数。第一个算位置，第二个算步长。

我个人习惯用链地址法，配合一个阈值——当链表长度超过 8 时，自动转换成红黑树。这样既保证了小数据量时的简单性，又防止了大数据量时的性能退化。

知识结构总览

下面这张图，把字符串哈希的核心逻辑串起来了。你可以看到，从原始字符串到最终的哈希表索引，中间经历了哪些步骤。

从图中可以看到，字符串哈希的流程并不复杂：拿到字符串，选一个算法，算出一个整数。但真正的挑战在于——选对算法，并且处理好碰撞。

我个人建议：如果你刚开始做项目，先用 BKDR 哈希，它简单、稳定、够用。等你对性能有更高要求时，再根据数据特征切换到 DJB 或 FNV。记住，没有万能的哈希算法，只有最适合你场景的算法。

---