字符串哈希详解，单hash，双hash，滚动哈希_C/C++

一、字符串哈希

1.1 基本概念

字符串哈希 将不同的字符串映射成不同的整数。

思想：将字符串映射成一个 p进制数字。

我们定义如下哈希函数：
$\begin{align} & hash(s) = \sum_{i=1}^{n}s[i]\times p^{n - i} (mod \ m) \\ & 其中s为长度为n的字符串，下标从1开始 \end{align}$
例如：p = 131，s = abc，其哈希值为 $97 \times {131}^2 + 98 \times 131 + 99$

显然，有时会存在多个不同的字符串哈希值相同的情况，我们通常的处理策略是巧妙设置p和m的值，往往取p为某个质数，m为某个大质数。

关于 p 的选择：常见的有131、31、13331等。

关于 m，由于 m 我们要取一个比较大的质数，而出题人往往对一些比较经典的质数如1e9 + 7、998244353等构造一堆卡哈希的数据，所以我们往往通过捕获一个随机数，根据随机数往下再取质数，来尽可能避免被hack。

还有的处理方式如：双模数hash，甚至三模数hash，虽然有一定作用，但是运算多了之后，时间复杂度的常数自然增大。

下面只介绍自然溢出法的单hash和双hash以及随机模底hash，多了也没必要，字符串哈希往往是作为算法优化的某一步骤，如果双hash都能被卡，说明题目可以采取其它优化策略，如：ac自动机、sa等。

1.2 实现方式

1.2.1 单hash（自然溢出法）

constexpr int base = 131;
std::vector<size_t> h(n + 1);
for (int i = 0; i < n; ++ i) {
    h[i + 1] = h[i] * base + s[i];
}

1.2.2 双hash（自然溢出法）

constexpr int base = 131;
std::vector<size_t> h1(n + 1), h2(n + 1);
for (int i = 0; i < n; ++ i) {
    h1[i + 1] = h1[i] * base1 + text[i];
    h2[i + 1] = h2[i] * base2 + text[i];
}

1.2.3 随机模底hash

随机模底哈希就是用随机数来生成base，同时抛弃自然溢出法，采用对一个大质数取模。

由于往往用时间戳生成随机数，所以被hack的几率也较小。但是，字符串哈希始终是有风险的。

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const int p = findprime(rng() % 900'000'000 + 900'000'000), 
base = uniform_int_distribution<>(8e8, 9e8)(rng);
std::vector<int> h(n + 1), p(n + 1);
p[0] = 1;
for (int i = 1; i <= n; ++ i)
    p[i] = 1ll * p[i - 1] * base % p;
for (int i = 0; i < n; ++ i) {
    h[i + 1] = (1ll * h[i] * base % p + text[i]) % p;
}

1.3 滚动hash

滚动哈希解决的问题：对于一个字符串，我们如何o(1)获取任意子串的hash值？

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

如上图，我们要获取蓝色部分的hash值，我们用类似前缀和的方式可以获取：

h(s(5, 8)) = h(8) - h(4) * base ^ 4

这种获取子串hash值得方式我们就称为滚动哈希。

1.4 oj 练习

1.4.1 模板

p3370 【模板】字符串哈希 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>

using i64 = long long;

bool isprime (int x) {
    if (x <= 1) return false;
    for (int i = 2; i * i <= x; ++ i)
        if (x % i == 0) 
            return false;
    return true;
}

int findprime (int x) {
    while (!isprime(x))
        ++ x;
    return x;
}


void solve() {
    std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

    const int p = findprime(rng() % 900'000'000 + 900'000'000), base = std::uniform_int_distribution<>(8e8, 9e8)(rng);

    int n;
    std::cin >> n;
    std::vector<int> a(n);

    for (int i = 0; i < n; i ++ ) {
        std::string s;
        std::cin >> s;
        int h = 0;
        for (char ch : s)
            h = (1ll * base * h + ch - '0') % p;
        a[i] = h;
    }

    std::sort(a.begin(), a.end());
    a.resize(std::unique(a.begin(), a.end()) - a.begin());
    
    std::cout << a.size();
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int _ = 1;
    // std::cin >> _;
    while (_ --)
        solve();
    return 0;
}

::cout.tie(nullptr);
int _ = 1;
// std::cin >> ;
while ( --)
solve();
return 0;
}