哈希，就是将一些内容转换为数字，一般可以用来压缩，替换等．

整数哈希#

我们先要取定一个模 MOD，然后将目标数字对 MOD 取余，其结果就是目标数字的哈希值．

两个不同的整数的哈希值可能相同，我们将其称为哈希冲突，为了避免哈希冲突，我们要将 MOD 定的大一些，且最好是一个质数．常用的 MOD 值有： $10^9+7$ ， $10^9+9$ ， $10^7+9$ ， $998244353$

以下代码可以生成一个整数的哈希值：

1
long long Hash(long long n, int mod)
2
{
3
    return n % mod;
4
}

字符串哈希#

为了获取一个字符串的哈希值，我们需要将字符串化作一个整数，由于 ASCII 一共有 128 格字符，所以最好的方式，就是将一个字符串视作一个 131 进制数（131 常被称为 base 基数，当然基数也可以是其他的一个小于模数且小于每一位的值域（字符串常为 127）的数字），然后将其转换为 10 进制数．

我们可以通过下面的代码将一个字符串转换为一个整数对 mod 取模的结果：

1
long long ans = 0;
2
for (int i = 0; i < str.size(); i++)
3
    ans = (ans * 128 + str[i]) % mod;

所以我们可以通过下面的函数来求字符串的哈希：

1
long long strHash(string str, int mod)
2
{
3
    long long ans = 0;
4
    for (int i = 0; i < str.size(); i++)
5
        ans = (ans * 127 + str[i]) % mod;
6
    return ans % mod;
7
}

当然，如果时间卡的比较紧，也可以使用自然溢出．

由于 unsigned long long 的溢出行为不是 UB，而是对 $2^{64}$ 取模．因此，可以使用 unsigned long long 的自然溢出．就类似于将 $2^{64}$ 当作模数．此时基数最好取一个随机的质数．自然溢出哈希法时间常数较少．

双哈希#

如果只进行一次哈希，特别容易进行哈希碰撞，所以，我们可以进行双哈希．

题目：P3370 字符串哈希

如题，给定 $N$ 个字符串（第 $i$ 个字符串长度为 $M_i$ ，字符串内包含数字、大小写字母，大小写敏感），请求出 $N$ 个字符串中共有多少个不同的字符串．

对于 $100\%$ 的数据： $N\leq 10000$ ， $M_i≈1000$ ， $M_{\max}\leq 1500$ ．

思路#

为了方便记录，我们定义以 $M$ 为模的哈希操作为 $hash_M$

对于这个题，我们可以使 h[i] 表示是否已经读取过了 $hash_M=i$ 的字符串．为了减少哈希冲突，我们可以使得当 h[i] 等于 $0$ 时，表示还没有 $hash_M=i$ 的字符串，否则，h[i] 表示 $hash_M=i$ 的字符串经过一次 $hash_N$ 的结果．

依照这个规定，我们每次记录一个字符串时，先检查 $h[hash_M]$ 是否为 $0$ ，如果这样，将 $h[hash_M]$ 设定为 $hash_N$ ，否则，先检查 $h[hash_M] = hash_N$ ，如果等于，那么说明这个字符串已经被记录过了，可以跳过，如果不等于，那么就表示发生了哈希冲突，我们通常将字符串储存到原位置的下一个空着的位置．

复杂度分析#

求一个字符串的哈希，其复杂度为 $O(m)$ ．但是如果需要移位，其复杂度就为 $O(n)$ ，现在有 $n$ 个字符串，那么其总复杂度就为 $O(n^2m)$ ．但是，由于移位只有极小概率会一直移到相同的位置（即发生哈希冲突），所以，可以近似的认为，其复杂度为 $O(nm)$ ，且在极端条件下会退化为 $O(n^2m)$ ，我们可以通过增大模数来减少哈希冲突，即减小移位的时间复杂度．

标程#

1
#include <bits/stdc++.h>
2
#define MOD1 (int)1e5 + 7
3
#define MOD2 (int)1e5 + 9
4
#define BASE 127
5
using namespace std;
6

7
long long Hash(string str, int mod)
8
{
9
    long long ans = 0;
10
    for (int i = 0; i < str.size(); i++)
11
        ans = (ans * BASE + str[i]) % mod;
12
    return ans % mod;
13
}
14

15
int h[MOD1 + 100];
16

17
int main()
18
{
19
    int n, ans = 0;
20
    cin >> n;
21
    for (int i = 1; i <= n; i++)
22
    {
23
        string str;
24
        cin >> str;
25
        long long hs1 = Hash(str, MOD1);
26
        long long hs2 = Hash(str, MOD2);
27
        while (h[hs1] != 0 && h[hs1] != hs2)
28
            hs1 = (hs1 + 1) % MOD1;
29
        if (h[hs1] == hs2)
30
            continue;
31
        if (h[hs1] == 0)
32
        {
33
            h[hs1] = hs2;
34
            ans++;
35
        }
36
    }
37
    cout << ans;
38
    return 0;
39
}

子串哈希#

对于一个字符串 $s$ ，已知其哈希为 $hash$ ，如何求其子串 $s1=s[l..r]$ 的哈希？

我们构造一个前缀哈希数组 h 和幂次数组 p，其中：

h[i+1] 表示字符串前 i+1 个字符 s[0..i] 的哈希值．
p[i+1] 表示右起第 i 位字符的权值， $p[i] = {base}^i$

1
h[0] = 0;
2
p[0] = 1;
3
for (int i = 0; i < n; i++) {
4
    h[i+1] = h[i] * base + s[i];
5
    p[i+1] = p[i] * base;
6
}

在计算时，使用 h[l] * p[r - l + 1] 将 s[0..l-1] 的哈希值“左移”r-l+1 位，用于抵消 s[0..r] 中的 s[0..l-1] 部分，代码如下：

1
long long get_hash(int l, int r) {
2
    return (h[r + 1] - h[l] * p[r - l + 1] % MOD + MOD) % MOD;
3
}

音乐

音乐