字符串哈希

字符串哈希就是将一个字符串映射为P进制的整数.

1. 将一个字符串映射成一个P进制整数
   对于一个长度为n的字符串s,这样定义一个Hash函数:\(h(s)=\sum_{i=1}^{n}s[i] \times p^{n-i}(mod M)\)
   例如,字符串,abc,其哈希值为\(ap^2 + bp^1 + c\)
2. 如果两个字符串不一样,哈希值却一样,这种现象称为哈希碰撞
3. 解决哈希碰撞的方法:
   巧妙地设置P和M的值,保证P与M互质.
   P通常取质数131或者13331
   M通常取大整数\(2^{64}\),把哈希函数值的数据类型定义为UUL(unsigned long long),超过则自动移除,等价于取模

练习

Luogu P3370 【模板】字符串哈希
解法一:😤

#include<bits/stdc++.h>
using namespace std;
int main(){
    unordered_map<string, int> m;
    int n;
    cin >> n;
    while(n -- ){
        string s;
        cin >> s;
        m[s] ++ ;
    }
    cout << m.size();
    return 0;
}

解法二:

热门相关：龙印战神   离婚合约：前妻的秘密   离婚合约：前妻的秘密   全天下都知道太子爱她   青莲剑说