字符串的哈希：BKDR 哈希算法

字符串哈希，说白了就是把一个字符串映射成一个整数。你想想看，比较两个字符串是否相等，最笨的办法是一个字符一个字符地比，O(n) 复杂度。但如果我能把每个字符串算出一个「指纹」，直接比两个整数，那就是 O(1) 了。这就是哈希的核心思想。

我个人习惯用 BKDR 哈希算法。为什么？因为它在实际工程中表现非常稳定，冲突率低，实现起来又简单。我在项目中处理过几百万条 URL 去重，用的就是它。

BKDR 哈希的原理

BKDR 算法的思路其实很朴素：把字符串看作一个 进制数。每个字符对应一个数字（比如 ASCII 码），然后乘以一个基数，累加起来。

公式长这样：

hash = 0
for each char c in string:
    hash = hash * seed + c

这里的 seed 是一个质数。为什么用质数？嗯，这里要注意：质数能减少哈希值的周期性重复，说白了就是让分布更均匀。我常用的 seed 是 131、1313、13131 这些。你问为什么是 131？其实没什么玄学，就是经验值，冲突率低。

代码实现

直接上代码。这是我项目里用过的版本，稍微改了一下拿来教学：

#include <stdio.h>
#include <string.h>

#define SEED 131
#define MOD 1000000007

unsigned long long bkdr_hash(const char *str) {
    unsigned long long hash = 0;
    while (*str) {
        hash = (hash * SEED + (unsigned char)(*str)) % MOD;
        str++;
    }
    return hash;
}

int main() {
    char s1[] = "hello";
    char s2[] = "world";
    printf("hash of '%s': %llu\n", s1, bkdr_hash(s1));
    printf("hash of '%s': %llu\n", s2, bkdr_hash(s2));
    return 0;
}

你看，核心代码就几行。但有个坑：unsigned char 的转换不能省。我曾经在解析 UTF-8 文本时忘了这个，结果中文字符的哈希值全乱套了——因为 char 默认是有符号的，负数的 ASCII 值会搞乱计算。

字符串哈希在去重中的应用

去重，说白了就是「来了一个字符串，先算哈希，看哈希表里有没有」。有就是重复，没有就存进去。

我做过一个日志分析工具，每天要处理上亿条 URL。每条 URL 都存字符串？内存扛不住。我的做法是：

1. 对每条 URL 算 BKDR 哈希（64 位整数）
2. 用哈希值作为 key，存到一个哈希集合里
3. 新来的 URL 先算哈希，查集合

这样每条 URL 只占 8 字节，而不是几百字节的字符串。内存直接省了 90% 以上。

字符串哈希在查找中的应用

查找和去重其实是一回事。但有一个经典场景：子串查找。

比如你要在长文本里找某个模式串。暴力法是 O(n*m)，用哈希可以做到 O(n)。怎么做？

• 先算模式串的哈希值
• 再算文本中每个等长子串的哈希值
• 比较哈希值，相等再逐字符确认（防止冲突）

这就是 Rabin-Karp 算法 的核心。我当年面试时手写过这个算法，面试官当场就说「嗯，基本功扎实」。

// 滚动哈希：快速计算下一个子串的哈希
// 假设已知 hash(s[i..i+m-1])，求 hash(s[i+1..i+m])
// 公式：new_hash = (old_hash - s[i] * pow_seed) * seed + s[i+m]
// 其中 pow_seed = seed^(m-1) % MOD

这个滚动技巧很实用。你想想看，每次重新算一个子串的哈希是 O(m)，但用滚动方式就是 O(1)。处理大文本时，性能差距是数量级的。

冲突处理

哈希不可能没有冲突。BKDR 虽然冲突率低，但你不能假设它为零。我的做法是：

场景	冲突处理方式
去重（允许极低概率误判）	直接信任哈希，不二次确认
精确查找	哈希匹配后，再逐字符比较
布隆过滤器	多个哈希函数，降低误判率

我曾经在做一个缓存系统时，偷懒没做二次确认。结果线上出现了两次哈希冲突，导致两个不同的用户名被当成同一个——用户登录时串号了。嗯，从那以后我再也不敢省略二次确认了。

SVG 流程图：BKDR 哈希与去重/查找的核心逻辑

总结一下

BKDR 哈希，说白了就是「字符串转大数」的经典实现。它简单、高效、冲突率低，是工程中最常用的字符串哈希算法之一。

• seed 选 131，模数选大质数
• 去重用哈希集合，内存省 90%
• 查找用滚动哈希，O(n) 搞定子串匹配
• 永远不要省略二次确认——除非你能接受那百万分之一的错误

我个人习惯在项目里把 BKDR 封装成一个工具函数，seed 和模数做成可配置的宏。这样换场景时改两个数字就行，不用动逻辑。你试试看，真的很顺手。