哈希 Hash

zifuneko · 2024-08-12 16:38:04 · 算法·理论

\text{Hash}:

• 哈希函数的基本性质：

  1. 输入参数的可能性是无限的，输出的值范围相对有限；
  2. 输入同样的样本一定得到同样的输出值，也就是哈希函数没有任何随机机制；
  3. 输入不同的样本也可能得到同样的输出值，此时叫哈希碰撞；
  4. 输入大量不同的样本，得到的大量输出值，会几乎均匀的分布在整个输出域上。

• 字符串哈希：把不同的字符串映射成不同的整数。

\text{Hash} 的特性:

• 减少哈希碰撞：使 p 与 M 互质，尽量增大 M。（p：即是 p 进制数）

• p$ 的常用值：$131$、$13331$、$433$、$499$、$599

没错！是玄学！但是非常好用！堪称赌狗的胜利！！

\text{P3370} 【模板】字符串哈希：

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
const int P = 131;
ULL v[10005];

ULL value(string s)
{
    ULL ans=s[0];
    for(int i=1; i<s.size(); i++) ans = ans*P + s[i];
    return ans;
}

int main()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin >> s;
        v[i] = value(s);
    }

    sort(v+1, v+n+1);
    int ans = 0;
    for(int i=1; i<=n; i++)
        if(v[i] != v[i+1]) ans ++;
    cout << ans;
    return 0;
}

求子串哈希

• 使用前缀思想快速求子串哈希；
• h[l, r] = h[r] - h[l-1] \times p ^ {r-l+1}