为什么以下代码对于计算字符串的哈希值是正确的？

Question

我目前正在阅读 Rabin Karp 算法，作为其中的一部分，我需要了解字符串多项式哈希。据我了解，字符串的哈希值由以下公式给出：

hash = ( char_0_val * p^0 + char_1_val * p^1 + ... + char_n_val ^ p^n ) mod m

其中：

char_i_val：是string[i]-'a' + 1
p是比字符集大的素数
m是一个大质数

网站 cp 算法有 following entry on the subject。他们说写上面的代码如下：

long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

我明白这个程序试图做什么，但我不明白为什么它是正确的。

我的问题

我无法理解为什么上面的代码是正确的。我已经很久没有做任何模块化数学了。在网上搜索后，我看到我们有以下模加和模乘公式：

a+b (mod m) = (a%m + b%m)%m
a*b (mod m) = (a%m * b%m)%m

基于以上，代码不应该是下面这样吗？

long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        int char_value = (c - 'a' + 1);
        hash_value = (hash_value%m + ((char_value%m * p_pow%m)%m)%m ) % m;
        p_pow = (p_pow%m * p%m) % m;
    }
    return hash_value;
}

我错过了什么？理想情况下，我正在寻求代码的分解以及第一个版本正确的原因的解释。

Answer 1

从数学上讲，没有理由以 m 为模减少中间结果。

在操作上，有几个非常密切相关的原因：

保持数字足够小，以便有效地表示它们。
使数字足够小，以使其上的操作不会溢出。

所以让我们看看一些数量，看看是否需要减少它们。

p 被定义为小于 m 的某个值，因此 p % m == p.
p_pow 和 hash_value 在计算时已经对模 m 进行了缩减，再次对模 m 进行缩减将无济于事。
char_value最多为26，已经小于m.
char_value * p_pow最多为26 * (m - 1)。这可能而且通常会超过 m。所以减少它模 m 会做一些事情。但是还是可以延迟，因为下一步还是“安全”的（不会溢出）
char_value * p_pow + hash_value 仍然最多 27 * (m - 1) 仍然远小于 2⁶³-1（long long 的最大值，请看下面为什么我假设 long long 是 64 位的），所以目前还没有问题。 m加后减模就好了

作为奖励，循环实际上可以在需要减少 hash_value模m。超过 3.41 亿次迭代！因此，出于大多数实际目的，您可以删除第一个 % m 和 return hash_value % m;。

我在这个计算中使用了 2⁶³-1 因为 p_pow = (p_pow * p) % m 要求 long long 是一个 64 位类型（或者，假设，一个奇异的36 位或更高的大小）。如果它是 32 位类型（这在技术上是允许的，但现在很少见）那么乘法可能会溢出，因为 p_pow 可能大约是十亿，而 32 位类型不能容纳 310 亿。

顺便说一下，这个散列函数专门用于只包含小写字母而没有其他任何内容的字符串。其他字符可能导致 char_value 的负值，这是个坏消息，因为 C++ 中的余数运算符 % 的工作方式使得对于负数它不是“模运算符”（用词不当，并且C++ 规范没有这样称呼它）。可以编写一个非常相似的函数，它可以将任何字符串作为输入，这会稍微改变上面的分析，但不会改变质量。

为什么以下代码对于计算字符串的哈希值是正确的？

Why is the following code correct for computing the hash of a string?

hash

polynomial-math

rabin-karp

modular-arithmetic

我的问题