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

整数哈希#

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

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

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

long long Hash(long long n, int mod)
{
    return n % mod;
}

cpp

字符串哈希#

为了获取一个字符串的哈希值，我们需要将字符串化作一个整数，由于 ASCII 一共有 128 格字符，所以最好的方式，就是将一个字符串视作一个 128 进制数，然后将其转换为 10 进制数．

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

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

cpp

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

long long strHash(string str, int mod)
{
    long long ans = 0;
    for (int i = 0; i < str.size(); i++)
        ans = (ans * 127 + str[i]) % mod;
    return ans % mod;
}

cpp

双哈希#

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

题目：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)$ ，我们可以通过增大模数来减少哈希冲突，即减小移位的时间复杂度．

标程#

#include <bits/stdc++.h>
#define MOD1 (int)1e5 + 7
#define MOD2 (int)1e5 + 9
using namespace std;

long long Hash(string str, int mod)
{
    long long ans = 0;
    for (int i = 0; i < str.size(); i++)
        ans = (ans * 127 + str[i]) % mod;
    return ans % mod;
}

int h[MOD1 + 100];

int main()
{
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string str;
        cin >> str;
        long long hs1 = Hash(str, MOD1);
        long long hs2 = Hash(str, MOD2);
        while (h[hs1] != 0 && h[hs1] != hs2)
            hs1 = (hs1 + 1) % MOD1;
        if (h[hs1] == hs2)
            continue;
        if (h[hs1] == 0)
        {
            h[hs1] = hs2;
            ans++;
        }
    }
    cout << ans;
    return 0;
}

cpp