字符串哈希：Rabin-Karp 与滚动哈希

在字符串匹配的经典教材里，KMP 和 Boyer-Moore 总是占据最大的篇幅。然而在工程实践中，真正被广泛部署的反而是 Rabin-Karp 及其衍生的滚动哈希家族——从 rsync 的增量传输到 git 的 pack 文件压缩，从抄袭检测到内容去重，滚动哈希以极低的实现复杂度覆盖了惊人数量的真实场景。

本文从多项式哈希的数学基础出发，逐步展开 Rabin-Karp 算法、Rabin 指纹、Buzhash、Content-Defined Chunking 等核心技术，并给出完整的 C 实现。文章不回避碰撞概率的严格分析，也不省略工程中踩过的坑。

一、多项式滚动哈希

基本定义

给定字符串 \(s = s_0 s_1 \cdots s_{m-1}\)，选取基数 \(b\) 和模数 \(p\)，其多项式哈希（polynomial rolling hash）定义为：

\[ H(s) = \left( \sum_{j=0}^{m-1} s_j \cdot b^{m-1-j} \right) \bmod p \]

这实质上是把字符串视为一个 \(b\) 进制整数，再对 \(p\) 取模。选择这个形式而非其他哈希构造，根本原因在于它支持常数时间的窗口滑动。

滚动更新公式

设当前窗口覆盖 \(s[i \ldots i+m)\)，其哈希值为 \(H_i\)。当窗口向右滑动一位时：

\[ H_{i+1} = \left( H_i - s_i \cdot b^{m-1} \right) \cdot b + s_{i+m} \bmod p \]

直觉上理解：把最高位（即将离开窗口的字符）减去，整体左移一位（乘以 \(b\)），再加上新进入窗口的字符。这个操作仅需 \(O(1)\) 时间，与窗口大小 \(m\) 无关。

参数选择

参数选择直接影响碰撞概率和计算效率：

对于 64 位无符号整数，一个实用的技巧是直接令 \(p = 2^{61} - 1\)（Mersenne 素数），利用其特殊结构可以用位运算代替昂贵的取模除法：

static inline uint64_t mod_mersenne61(unsigned __int128 x) {
    uint64_t lo = (uint64_t)x & ((1ULL << 61) - 1);
    uint64_t hi = (uint64_t)(x >> 61);
    uint64_t r = lo + hi;
    return r >= ((1ULL << 61) - 1) ? r - ((1ULL << 61) - 1) : r;
}

二、Rabin-Karp 算法

算法流程

Rabin-Karp 算法由 Michael Rabin 和 Richard Karp 于 1987 年提出，其核心思路极其简洁：

1. 预计算模式串 \(P\) 的哈希值 \(H_P\)。
2. 用滚动哈希遍历文本 \(T\) 的所有长度为 \(m\) 的窗口。
3. 当 \(H_{win} = H_P\) 时，逐字符比较确认是否为真匹配。

这个”哈希先筛、字符再验”的两阶段策略是算法的精髓。第一阶段以 \(O(1)\) 排除绝大多数不匹配位置，第二阶段仅在少量候选位置执行昂贵的逐字符比较。

复杂度分析

• 预处理：\(O(m)\)，计算模式串哈希和 \(b^{m-1} \bmod p\)。
• 期望时间：\(O(n + m)\)，假设哈希函数足够均匀，虚假匹配（false positive）的期望次数为 \(O(n/p)\)。
• 最坏时间：\(O(nm)\)，当所有窗口都产生哈希碰撞时退化。例如 \(T = \text{"aaa...a"}\)、\(P = \text{"aaa...a"}\)（一字之差在尾部）。

与 KMP/BM 的定位差异

Rabin-Karp 的优势不在单模式匹配的最坏复杂度上——KMP 和 Boyer-Moore 都保证了 \(O(n)\) 最坏时间。Rabin-Karp 真正闪光的地方是：

1. 多模式匹配：将所有模式串的哈希值放入哈希表，一次扫描即可匹配多个模式，无需为每个模式构建自动机。
2. 实现简单：核心逻辑不到 30 行，而 KMP 的 failure function 和 BM 的 good suffix rule 实现起来容易出错。
3. 可扩展性：很容易扩展为二维匹配、近似匹配等变体。

三、碰撞概率分析

单次碰撞概率

对于两个不同的长度为 \(m\) 的字符串 \(s \ne t\)，多项式哈希 \(H(s) = H(t) \pmod{p}\) 等价于 \(b\) 是多项式 \(f(x) = \sum (s_j - t_j) x^{m-1-j}\) 模 \(p\) 的根。由 Schwartz-Zippel 引理，这样的根至多 \(m-1\) 个，因此：

\[ \Pr[H(s) = H(t)] \le \frac{m - 1}{p} \]

当 \(p \approx 10^9\)、\(m = 1000\) 时，单次碰撞概率约 \(10^{-6}\)，看起来很低。但在长文本匹配中，我们要对 \(n - m + 1\) 个窗口分别比较，至少出现一次虚假匹配的概率上界为：

\[ \Pr[\text{any false positive}] \le \frac{(n - m + 1)(m - 1)}{p} \]

对于 \(n = 10^6\)、\(m = 10^3\)、\(p = 10^9 + 7\)，这个概率约为 \(10^{-3} \times 10^3 / 10^9 = 10^{-3}\)——完全可接受。但如果对手可以构造输入（如在线评测系统），情况就不同了。

对抗性碰撞构造

如果攻击者已知 \(b\) 和 \(p\)，他可以精确构造碰撞。一个典型的攻击是：

1. 选择任意字符串 \(s\)。
2. 计算 \(H(s)\)。
3. 修改 \(s\) 的两个位置使哈希值不变：在位置 \(j_1\) 加 \(\delta\)，在位置 \(j_2\) 减 \(\delta \cdot b^{j_1 - j_2}\)。

这在竞赛和安全场景中是真实威胁。因此需要反碰撞技术（详见第七节）。

生日悖论视角

如果我们需要对 \(k\) 个不同字符串计算哈希（例如在去重场景中），由生日悖论，出现至少一对碰撞的概率在 \(k \approx \sqrt{p}\) 时达到约 50%。对于 \(p = 10^9 + 7\)，大约 \(k \approx 31623\) 个字符串就可能碰撞。这再次提醒我们：单哈希在大规模场景中是不够的。

四、Rabin 指纹：GF(2) 上的不可约多项式

从整数域到有限域

前面讨论的多项式哈希工作在整数模 \(p\) 上。Michael Rabin 在 1981 年提出了另一种构造——Rabin fingerprint，它工作在 \(\text{GF}(2)\) 上的多项式环中。

在 \(\text{GF}(2)\) 中，加法是 XOR，乘法是 AND。一个比特串 \(b_0 b_1 \cdots b_{n-1}\) 被视为 \(\text{GF}(2)[x]\) 中的多项式：

\[ A(x) = b_0 x^{n-1} + b_1 x^{n-2} + \cdots + b_{n-1} \]

Rabin fingerprint 选择一个 \(k\) 次不可约多项式 \(P(x) \in \text{GF}(2)[x]\)，定义指纹为：

\[ \text{fp}(A) = A(x) \bmod P(x) \]

为什么选择不可约多项式

不可约多项式在 \(\text{GF}(2)[x]\) 中的地位等同于质数在整数中的地位。选择不可约的 \(P(x)\) 保证了商环 \(\text{GF}(2)[x] / P(x)\) 是一个有 \(2^k\) 个元素的有限域，从而使碰撞概率分析有坚实的数学基础。

具体而言，对于两个不同的长度为 \(n\) 的比特串，其 Rabin fingerprint 碰撞的概率为：

\[ \Pr[\text{collision}] \le \frac{n}{2^k} \]

这里 \(k\) 是指纹位数。取 \(k = 64\) 时，即使 \(n = 2^{30}\)（约 10 亿位），碰撞概率也仅约 \(2^{-34}\)。

滚动更新

Rabin fingerprint 同样支持滚动更新。当一个比特从窗口左端移出、一个新比特从右端进入时，更新公式为：

\[ \text{fp}_{i+1} = ((\text{fp}_i \oplus b_i \cdot x^{w-1}) \cdot x) \oplus b_{i+w} \bmod P(x) \]

所有运算都是 \(\text{GF}(2)\) 上的，实现时就是 XOR 和移位。现代 CPU 上，如果 \(P(x)\) 选择得当（如配合 PCLMULQDQ 指令），这个运算极其高效。

常用不可约多项式

以下是几个常用的不可约多项式：

需要强调的是：CRC 和 Rabin fingerprint 共享 \(\text{GF}(2)\) 多项式除法的数学结构，但它们的设计目标不同。CRC 针对突发错误检测优化，而 Rabin fingerprint 针对随机碰撞概率的理论保证优化。

五、Karp-Rabin 多模式匹配

动机

考虑这样一个场景：给定一组模式串 \(P_1, P_2, \ldots, P_k\)（长度均为 \(m\)），在文本 \(T\) 中找出所有匹配。朴素方法是对每个模式串分别运行匹配，总时间 \(O(kn)\)。Aho-Corasick 自动机可以做到 \(O(n + km + z)\)（\(z\) 为匹配数），但实现复杂。

Karp-Rabin 多模式方案提供了一个优雅的中间地带：

1. 将所有 \(k\) 个模式串的哈希值存入哈希集合 \(S\)。
2. 用滚动哈希扫描文本，每个窗口的哈希值在 \(S\) 中查找。
3. 命中时逐字符验证。

总时间为 \(O(n + km)\)（期望），实现不到 50 行代码。

不等长模式的处理

当模式串长度不一时，一种方法是按长度分组，每组分别扫描。但这在长度种类多时效率低下。更好的做法是：

1. 找到最短模式长度 \(m_{\min}\)。
2. 对所有模式串，只取前 \(m_{\min}\) 个字符计算”前缀哈希”。
3. 用长度 \(m_{\min}\) 的滑动窗口扫描文本。
4. 前缀哈希命中后，再用完整长度验证。

这个两级过滤策略在实践中效果很好，前提是 \(m_{\min}\) 不能太小（否则前缀哈希区分力不足）。

实际应用：抄袭检测

学术界和工业界的抄袭检测系统（如 MOSS、Turnitin）广泛使用滚动哈希的变体。典型流程是：

1. 对文档进行词法归一化（去除空白、统一大小写等）。
2. 对归一化后的 token 序列计算 \(k\)-gram 的滚动哈希。
3. 使用 winnowing 算法选取代表性指纹子集。
4. 比较不同文档的指纹集合，计算相似度。

滚动哈希在这里的角色是高效生成所有 \(k\)-gram 的指纹，使得后续比较可以在指纹级别进行，而非原始文本级别。

六、Buzhash：循环多项式哈希

设计动机

多项式滚动哈希有一个潜在弱点：乘法和取模运算在某些架构上仍然相对昂贵。Buzhash（也称 cyclic polynomial hash）用位旋转（barrel shift）和 XOR 代替乘法和取模，在保持滚动性质的同时获得更高的吞吐。

算法定义

1. 预计算一个随机查找表 \(H_{\text{tab}}[c]\)，为每个字符 \(c\) 分配一个随机的 \(k\) 位整数。
2. 定义位旋转操作 \(\text{rot}^n(x)\)：将 \(x\) 循环左移 \(n\) 位。
3. 窗口 \(s[i \ldots i+w)\) 的 Buzhash 值为：

\[ B = \text{rot}^{w-1}(H_{\text{tab}}[s_i]) \oplus \text{rot}^{w-2}(H_{\text{tab}}[s_{i+1}]) \oplus \cdots \oplus H_{\text{tab}}[s_{i+w-1}] \]

滚动更新

\[ B_{i+1} = \text{rot}^1(B_i) \oplus \text{rot}^w(H_{\text{tab}}[s_i]) \oplus H_{\text{tab}}[s_{i+w}] \]

整个更新只需一次旋转、两次 XOR 和两次表查找，没有乘法和除法。在分支预测友好的场景下，每字节的处理时间可以低至 2-3 个时钟周期。

碰撞分析

Buzhash 的碰撞分析不如多项式哈希那样干净。它的安全性依赖于查找表的随机性。如果查找表被视为随机预言机，则对于随机输入，\(k\) 位 Buzhash 的碰撞概率约为 \(2^{-k}\)。但在对抗性场景下，攻击者如果知道查找表，可以利用 XOR 的线性性质高效构造碰撞。

适用场景

Buzhash 最常用于对性能敏感但安全性要求不高的场景：

• 内容定义分块（Content-Defined Chunking）
• 局部敏感哈希（Locality-Sensitive Hashing）的预处理
• 实时流数据的指纹提取

七、反哈希碰撞技术

在竞赛和安全相关的场景中，单一哈希极易被攻击。以下是主流的防御手段。

双哈希（Double Hashing）

同时使用两组独立的 \((b_1, p_1)\) 和 \((b_2, p_2)\)，只有当两个哈希值都匹配时才认为字符串相等。碰撞概率降至：

\[ \Pr[\text{collision}] \le \frac{m-1}{p_1} \cdot \frac{m-1}{p_2} \]

取 \(p_1, p_2 \approx 10^9\) 时，对于 \(m = 10^3\)，概率约 \(10^{-12}\)——在实际中可以认为不可能碰撞。

typedef struct {
    uint64_t h1;
    uint64_t h2;
} DoubleHash;

static inline DoubleHash double_hash_update(
    DoubleHash prev, int out_char, int in_char,
    uint64_t b1, uint64_t p1, uint64_t bm1,
    uint64_t b2, uint64_t p2, uint64_t bm2)
{
    DoubleHash next;
    next.h1 = ((prev.h1 - (uint64_t)out_char % p1 * bm1 % p1 + p1) % p1 * b1 + in_char) % p1;
    next.h2 = ((prev.h2 - (uint64_t)out_char % p2 * bm2 % p2 + p2) % p2 * b2 + in_char) % p2;
    return next;
}

随机基数（Random Base）

在程序启动时随机选择基数 \(b\)，使攻击者无法提前构造碰撞。这在在线评测系统中是常用策略：

#include <stdlib.h>
#include <time.h>

uint64_t random_base(void) {
    srand((unsigned)time(NULL) ^ (unsigned)getpid());
    return (uint64_t)rand() % 1000000000 + 256;
}

这里下界 256 确保基数大于所有 ASCII 字符值。

多次采样

对于需要比较大量字符串对的场景（如去重），可以对每个字符串取 \(t\) 个独立哈希值。只有当所有 \(t\) 个哈希值都匹配时才认为相等。碰撞概率指数级下降：

\[ \Pr[\text{collision}] \le \left(\frac{m}{p}\right)^t \]

技术对比

八、Content-Defined Chunking（CDC）

问题背景

在数据去重和增量同步场景中，一个核心问题是：如何将文件分割成块（chunk），使得文件中间的插入或删除只影响局部块，而不导致后续所有块的边界移位？

固定大小分块（例如每 4KB 一块）无法做到这一点——在偏移量 0 处插入一个字节，后续所有块都会改变。

CDC 的原理

Content-Defined Chunking 用滚动哈希解决这个问题：

1. 在文件上滑动一个宽度为 \(w\) 的窗口，计算滚动哈希 \(H\)。
2. 当 \(H \bmod D = r\)（\(D\) 是除数，\(r\) 是预选余数）时，在此处切分。
3. 由于切分条件只依赖于窗口内的内容，与绝对位置无关，因此中间的插入删除不会影响远处的切分边界。

块大小控制

设 \(D = 2^d\)，则平均块大小为 \(2^d\) 字节。但实际块大小服从几何分布，方差很大。工程中通常加入最小块大小 \(L_{\min}\) 和最大块大小 \(L_{\max}\) 的限制：

• 在 \(L_{\min}\) 之前，不检查切分条件。
• 超过 \(L_{\max}\) 时，强制切分。

Fastcdc 算法进一步引入了两级掩码策略：在正常块大小附近使用较严格的掩码，在偏离正常大小时使用较宽松的掩码，以获得更紧凑的块大小分布。

典型参数

CDC 的去重效果

假设一个 1 GiB 的文件在中间修改了 100 字节。固定分块方案可能导致修改点之后的所有块全部改变，增量传输需要约 500 MiB。而 CDC 方案下，只有修改点附近的 1-3 个块发生变化，增量传输仅需几十 KiB。

这就是 rsync 和各种备份工具采用 CDC 的根本原因。

九、完整 C 实现

以下是一个完整的 C 实现，包含 Rabin-Karp 字符串匹配和基于 Rabin fingerprint 的 Content-Defined Chunking，共约 200 行。

/* string_hash.c — Rabin-Karp 匹配 + Content-Defined Chunking
 *
 * 编译: gcc -O2 -std=c11 -o string_hash string_hash.c
 * 用法: ./string_hash
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <assert.h>

/* ========================================================================
 *  第一部分：多项式滚动哈希 — Rabin-Karp 字符串匹配
 * ======================================================================== */

#define RK_BASE  131ULL
#define RK_MOD   1000000007ULL

/* 计算 base^exp mod m */
static uint64_t power_mod(uint64_t base, uint64_t exp, uint64_t m)
{
    uint64_t result = 1;
    base %= m;
    while (exp > 0) {
        if (exp & 1)
            result = (unsigned __int128)result * base % m;
        base = (unsigned __int128)base * base % m;
        exp >>= 1;
    }
    return result;
}

/* 计算字符串的多项式哈希值 */
static uint64_t poly_hash(const char *s, int len, uint64_t base, uint64_t mod)
{
    uint64_t h = 0;
    for (int i = 0; i < len; i++)
        h = ((unsigned __int128)h * base + (unsigned char)s[i]) % mod;
    return h;
}

/*
 * rabin_karp_search — 在 text 中查找 pattern 的所有出现位置
 *
 * 返回匹配位置数量，匹配位置存入 positions 数组（调用方分配）。
 * max_results 限制最大返回数量。
 */
int rabin_karp_search(const char *text, int n,
                      const char *pattern, int m,
                      int *positions, int max_results)
{
    if (m > n || m == 0)
        return 0;

    int count = 0;
    uint64_t base = RK_BASE, mod = RK_MOD;

    /* 预计算 base^(m-1) mod p */
    uint64_t bm = power_mod(base, (uint64_t)(m - 1), mod);

    /* 模式串哈希 */
    uint64_t hp = poly_hash(pattern, m, base, mod);

    /* 文本首窗口哈希 */
    uint64_t ht = poly_hash(text, m, base, mod);

    for (int i = 0; i <= n - m; i++) {
        if (ht == hp) {
            /* 哈希匹配，逐字符验证 */
            if (memcmp(text + i, pattern, (size_t)m) == 0) {
                if (count < max_results)
                    positions[count] = i;
                count++;
            }
        }
        /* 滚动到下一个窗口 */
        if (i < n - m) {
            ht = ((unsigned __int128)(ht + mod
                  - (unsigned __int128)(unsigned char)text[i] * bm % mod)
                  * base
                  + (unsigned char)text[i + m]) % mod;
        }
    }
    return count;
}

/*
 * rabin_karp_multi — 多模式匹配
 *
 * patterns 是 k 个等长（长度 m）模式串的数组。
 * 返回各模式是否在 text 中出现（results[j] = 1 表示 patterns[j] 出现过）。
 */
void rabin_karp_multi(const char *text, int n,
                      const char **patterns, int k, int m,
                      int *results)
{
    if (m > n || m == 0 || k == 0)
        return;

    memset(results, 0, sizeof(int) * (size_t)k);

    uint64_t base = RK_BASE, mod = RK_MOD;
    uint64_t bm = power_mod(base, (uint64_t)(m - 1), mod);

    /* 将所有模式串的哈希放入简易哈希表（开放寻址） */
    int tbl_size = k * 4;           /* 装载因子 <= 25% */
    uint64_t *tbl_hash = calloc((size_t)tbl_size, sizeof(uint64_t));
    int      *tbl_idx  = malloc((size_t)tbl_size * sizeof(int));
    int      *tbl_used = calloc((size_t)tbl_size, sizeof(int));

    for (int j = 0; j < k; j++) {
        uint64_t h = poly_hash(patterns[j], m, base, mod);
        int slot = (int)(h % (uint64_t)tbl_size);
        while (tbl_used[slot])
            slot = (slot + 1) % tbl_size;
        tbl_hash[slot] = h;
        tbl_idx[slot]  = j;
        tbl_used[slot] = 1;
    }

    /* 滚动扫描 */
    uint64_t ht = poly_hash(text, m, base, mod);

    for (int i = 0; i <= n - m; i++) {
        int slot = (int)(ht % (uint64_t)tbl_size);
        while (tbl_used[slot]) {
            if (tbl_hash[slot] == ht) {
                int j = tbl_idx[slot];
                if (!results[j] && memcmp(text + i, patterns[j], (size_t)m) == 0)
                    results[j] = 1;
            }
            slot = (slot + 1) % tbl_size;
        }
        if (i < n - m) {
            ht = ((unsigned __int128)(ht + mod
                  - (unsigned __int128)(unsigned char)text[i] * bm % mod)
                  * base
                  + (unsigned char)text[i + m]) % mod;
        }
    }

    free(tbl_hash);
    free(tbl_idx);
    free(tbl_used);
}

/* ========================================================================
 *  第二部分：Content-Defined Chunking（CDC）
 *  使用 Buzhash（循环多项式）作为滚动哈希
 * ======================================================================== */

#define CDC_WINDOW    48
#define CDC_MIN_CHUNK 2048
#define CDC_MAX_CHUNK 65536
#define CDC_AVG_BITS  13           /* 平均块大小 = 2^13 = 8192 */
#define CDC_MASK      ((1ULL << CDC_AVG_BITS) - 1)

/* 随机查找表（每字节一个 64 位随机值） */
static uint64_t buzhash_table[256];

static void buzhash_init_table(uint64_t seed)
{
    /* 简易 xorshift64 PRNG */
    uint64_t s = seed;
    for (int i = 0; i < 256; i++) {
        s ^= s << 13;
        s ^= s >> 7;
        s ^= s << 17;
        buzhash_table[i] = s;
    }
}

static inline uint64_t rotl64(uint64_t x, int n)
{
    n &= 63;
    return (x << n) | (x >> (64 - n));
}

/*
 * cdc_chunk — 对 data[0..len) 进行 Content-Defined Chunking
 *
 * 将每个块的 (offset, length) 写入 chunks 数组，返回块数。
 */
typedef struct { int offset; int length; } Chunk;

int cdc_chunk(const unsigned char *data, int len,
              Chunk *chunks, int max_chunks)
{
    if (len == 0)
        return 0;

    int count = 0;
    int pos   = 0;

    while (pos < len && count < max_chunks) {
        int remaining = len - pos;
        if (remaining <= CDC_MIN_CHUNK) {
            /* 剩余数据不足最小块，作为最后一块 */
            chunks[count].offset = pos;
            chunks[count].length = remaining;
            count++;
            break;
        }

        /* 初始化 Buzhash 窗口 */
        uint64_t hash = 0;
        int start = pos + CDC_MIN_CHUNK - CDC_WINDOW;
        if (start < pos)
            start = pos;

        for (int j = 0; j < CDC_WINDOW && (start + j) < len; j++)
            hash ^= rotl64(buzhash_table[data[start + j]],
                           CDC_WINDOW - 1 - j);

        int cut = -1;
        int end = pos + CDC_MAX_CHUNK;
        if (end > len)
            end = len;

        for (int i = pos + CDC_MIN_CHUNK; i < end; i++) {
            /* 滚动更新 Buzhash */
            int out_idx = i - CDC_WINDOW;
            if (out_idx >= pos) {
                hash = rotl64(hash, 1)
                     ^ rotl64(buzhash_table[data[out_idx]], CDC_WINDOW)
                     ^ buzhash_table[data[i]];
            }

            if ((hash & CDC_MASK) == 0) {
                cut = i + 1;
                break;
            }
        }

        if (cut < 0)
            cut = end;       /* 达到最大块大小，强制切分 */

        chunks[count].offset = pos;
        chunks[count].length = cut - pos;
        count++;
        pos = cut;
    }

    return count;
}

/* ========================================================================
 *  第三部分：演示主函数
 * ======================================================================== */

static void demo_rabin_karp(void)
{
    printf("=== Rabin-Karp 单模式匹配 ===\n");

    const char *text    = "abracadabrabracabracadabra";
    const char *pattern = "abra";
    int n = (int)strlen(text);
    int m = (int)strlen(pattern);

    int positions[64];
    int count = rabin_karp_search(text, n, pattern, m, positions, 64);

    printf("  Text:    \"%s\"\n", text);
    printf("  Pattern: \"%s\"\n", pattern);
    printf("  Found %d occurrence(s):", count);
    for (int i = 0; i < count && i < 64; i++)
        printf(" %d", positions[i]);
    printf("\n\n");
}

static void demo_multi_match(void)
{
    printf("=== Rabin-Karp 多模式匹配 ===\n");

    const char *text = "the quick brown fox jumps over the lazy dog";
    const char *patterns[] = {"fox", "the", "dog", "cat", "owl"};
    int k = 5, m = 3;
    int results[5];

    rabin_karp_multi(text, (int)strlen(text), patterns, k, m, results);

    for (int j = 0; j < k; j++)
        printf("  \"%s\" : %s\n", patterns[j],
               results[j] ? "found" : "not found");
    printf("\n");
}

static void demo_cdc(void)
{
    printf("=== Content-Defined Chunking ===\n");

    buzhash_init_table(0xDEADBEEFCAFE1234ULL);

    /* 生成伪随机测试数据 */
    int data_len = 256 * 1024;     /* 256 KiB */
    unsigned char *data = malloc((size_t)data_len);
    uint64_t rng = 42;
    for (int i = 0; i < data_len; i++) {
        rng ^= rng << 13;
        rng ^= rng >> 7;
        rng ^= rng << 17;
        data[i] = (unsigned char)(rng & 0xFF);
    }

    Chunk chunks[1024];
    int nchunks = cdc_chunk(data, data_len, chunks, 1024);

    printf("  Data size: %d bytes\n", data_len);
    printf("  Chunks:    %d\n", nchunks);
    if (nchunks > 0) {
        int min_sz = chunks[0].length, max_sz = chunks[0].length;
        long total = 0;
        for (int i = 0; i < nchunks; i++) {
            if (chunks[i].length < min_sz) min_sz = chunks[i].length;
            if (chunks[i].length > max_sz) max_sz = chunks[i].length;
            total += chunks[i].length;
        }
        printf("  Avg size:  %ld bytes\n", total / nchunks);
        printf("  Min size:  %d bytes\n", min_sz);
        printf("  Max size:  %d bytes\n", max_sz);
    }
    printf("\n");

    free(data);
}

int main(void)
{
    demo_rabin_karp();
    demo_multi_match();
    demo_cdc();
    return 0;
}

十、基准测试：Rabin-Karp vs KMP vs Boyer-Moore

在讨论算法优劣时，纸面上的渐近复杂度只是一半的故事。另一半来自实测数据。以下是在一台配备 Intel i7-12700K（单核 Turbo 5.0 GHz）、32 GB DDR5 的机器上，对三种算法进行的基准测试。

测试条件

• 文本：英文维基百科前 100 MiB（enwiki-100m.txt）。
• 模式串：从文本中随机抽取 5 个不同长度的子串。
• 编译器：GCC 13.2，-O2 -march=native。
• 每组测试重复 10 次取中位数。

结果

分析

1. Boyer-Moore 在单模式匹配中全面胜出，这并不意外——BM 的亚线性性能来自于跳过大量不需要检查的位置，而 RK 和 KMP 必须逐字节扫描。

2. Rabin-Karp 在单模式匹配中略慢于 KMP，主要原因是每步需要一次取模运算（即使用了 Mersenne 素数优化也有开销）。

3. 但 Rabin-Karp 在多模式匹配中逆转局面：

Rabin-Karp 的多模式扫描时间几乎不随模式数增长——代价仅是哈希表查找从 \(O(1)\) 略微增加。而逐个运行 BM 的时间线性增长。Aho-Corasick 在构建自动机后同样高效，但其预处理时间和内存消耗远高于 RK。

何时选择 Rabin-Karp

• 多模式匹配且模式集合动态变化（不值得预建自动机）。
• 需要快速原型，代码行数有严格限制。
• 匹配逻辑需要嵌入更大的滑动窗口框架（如 CDC、相似度检测）。
• 二维模式匹配。

十一、真实世界应用

rsync 的增量传输

rsync 的增量传输协议是 CDC 最早和最成功的应用之一：

1. 接收方将本地文件按固定大小分块，计算每块的弱哈希（Adler-32 的变体，本质上是一种滚动哈希）和强哈希（MD5 或 xxHash）。
2. 弱哈希和强哈希发送给发送方。
3. 发送方在新版本文件上用滚动哈希扫描，寻找弱哈希匹配。
4. 弱哈希匹配后用强哈希确认，匹配的块只传输引用，不匹配的部分传输原始数据。

这里滚动哈希承担了”快速筛选”的角色，与 Rabin-Karp 中的角色完全一致。

git pack 文件

git 的 pack 文件格式使用 delta 压缩来减少存储空间。在寻找 delta 基底时，git 使用滚动哈希来高效比较对象之间的相似区域。具体来说，git pack-objects 中的 delta 搜索使用了一个类似 rsync 的滑动窗口方案。

抄袭检测

MOSS（Measure Of Software Similarity）是学术界最著名的代码抄袭检测系统。其核心算法 winnowing 基于以下步骤：

1. 对代码进行词法分析和归一化。
2. 计算所有 \(k\)-gram 的滚动哈希。
3. 在每个长度为 \(w\) 的窗口中选择最小哈希值作为指纹。
4. 比较文档之间的指纹集合重叠度。

数据库中的模糊连接

在大规模数据集的模糊连接（fuzzy join）中，滚动哈希可以用来快速计算字符串之间的 \(n\)-gram 重叠度。例如，两个字符串的 Jaccard 相似度可以通过比较它们的 \(n\)-gram 指纹集合来近似估算。

网络入侵检测

深度包检测（DPI）系统需要在网络流量中实时搜索大量恶意模式。Rabin-Karp 的多模式匹配变体在这里特别有用，因为模式集合可能频繁更新（新的恶意签名），而 Aho-Corasick 自动机的重建成本较高。

十二、工程陷阱与个人观点

工程陷阱速查表

个人观点

滚动哈希是字符串算法工具箱中投入产出比最高的工具。 我在工程实践中反复验证了这个结论。原因如下：

第一，它的概念极其简单。不像 KMP 的失配函数或后缀自动机的转移表那样需要反复推演才能理解正确性，多项式哈希的数学基础就是一个模运算的多项式求值，任何学过数论基础的人都能在五分钟内理解。

第二，它的扩展性无与伦比。从单模式匹配到多模式匹配，从一维字符串到二维矩阵，从精确匹配到近似匹配，从字符串搜索到文件分块——同一个核心思想（滑动窗口 + 增量更新哈希）适用于所有这些场景。而 KMP 和 BM 基本上只适用于一维精确单模式匹配。

第三，它对工程环境的适应力极强。需要在嵌入式系统上跑？不依赖任何复杂数据结构，几十行 C 代码就够了。需要在 GPU 上并行化？每个线程独立维护一个滚动哈希窗口，几乎不需要线程间通信。需要在分布式系统中做去重？每个节点独立分块，块边界由内容决定，天然支持分布式一致性。

当然，滚动哈希不是万能的。在单模式匹配的最坏情况下，它不如 KMP 和 BM。在需要密码学安全的场景中，它无法替代 SHA-256 或 BLAKE3。在需要精确计算编辑距离的场景中，它帮不上忙。

但如果你只能带一个字符串算法上战场——我会毫不犹豫地选择滚动哈希。

关于 CDC 的未来。 随着 NVMe SSD 的普及和网络带宽的增长，数据去重和增量同步的重要性只增不减。我预期 CDC 技术会在更多场景中被采用：容器镜像分发、数据库备份、边缘计算中的模型更新同步等。而 CDC 的核心，就是一个好的滚动哈希。

关于竞赛中的字符串哈希。 在算法竞赛中，字符串哈希经常被视为”不够优雅”的解法——相比后缀数组、后缀自动机这些”正解”，字符串哈希似乎显得太简单、太暴力。但我认为这种偏见是错误的。在实际比赛中，字符串哈希往往是最快写出、最不容易写错、时间复杂度也完全可接受的方案。双哈希加随机基数的碰撞概率低到可以忽略不计。如果目标是拿分而非炫技，字符串哈希经常是最优选择。

关于 Rabin fingerprint vs 多项式哈希的选择。 在纯软件实现中，多项式哈希通常更快——整数乘法在现代 CPU 上只需 3-4 个周期，而 GF(2) 多项式乘法如果不借助 PCLMULQDQ 指令则需要更多。但如果目标平台支持 carry-less multiplication 指令（x86 从 Westmere 开始支持，ARM 从 ARMv8 开始通过 PMULL 支持），Rabin fingerprint 的吞吐量可以非常高。此外，Rabin fingerprint 的碰撞概率分析更干净（不依赖于基数的选择），这在需要严格理论保证的场景中是一个优势。

最后，无论选择哪种滚动哈希，都要记住一条铁律：永远不要信任单一哈希值。 在任何哈希匹配之后都要做验证——要么逐字节比较，要么用第二个独立哈希再确认。这个原则适用于 Rabin-Karp 匹配、CDC 去重、以及所有基于哈希的相等性判断。碰撞是概率问题，不是”会不会发生”的问题，而是”什么时候发生”的问题。

参考文献

1. Karp, R. M., & Rabin, M. O. (1987). Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, 31(2), 249-260.
2. Rabin, M. O. (1981). Fingerprinting by random polynomials. Technical Report TR-15-81, Center for Research in Computing Technology, Harvard University.
3. Lemire, D., & Kaser, O. (2010). Recursive n-gram hashing is pairwise independent, at best. Computer Speech & Language, 24(4), 698-710.
4. Xia, W., et al. (2016). A comprehensive study of the past, present, and future of data deduplication. Proceedings of the IEEE, 104(9), 1681-1710.
5. Schleimer, S., Wilkerson, D. S., & Aiken, A. (2003). Winnowing: Local algorithms for document fingerprinting. SIGMOD ’03.
6. Muthitacharoen, A., Chen, B., & Mazieres, D. (2001). A low-bandwidth network file system. SOSP ’01.

上一篇: 编辑距离与模糊匹配 下一篇: SIMD 字符串处理 相关阅读: - 密码学哈希 vs 非密码学哈希 - 一致性哈希