hash入门
只讨论最常用的进制哈希。
例题
题意：求 N 个字符串中有多少个不同的字符串（$N leq 10^4$）。
分析：
对每个字符串求一次哈希值，然后统计有多少个不同的哈希值。
单哈希
选择一个大质数，或者自然溢出。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const ull base = 233; ull mod=212370440130137957ll; const int maxn = 10000+10; int n; ull f[maxn]; char s[maxn]; ull Hash(char s[]) //自然溢出 { ull ans = 0; int len = strlen(s); for(int i = 0;i < len;i++) { ans = (base*ans + (ull)s[i]) % mod; } return ans; } set<ull>st; int main() { scanf("%d", &n); for(int i = 0;i < n;i++) { scanf("%s", s); st.insert(Hash(s)); } printf("%d ", st.size()); }
双哈希
采用两个模数，哈希冲突的概率会降低很多，但常数会增大。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const ull base = 233; ull mod1 = 212370440130137957ll; ull mod2 = 1 << 30; const int maxn = 10000+10; int n; char s[maxn]; ull Hash1(char s[]) //自然溢出 { ull ans = 0; int len = strlen(s); for(int i = 0;i < len;i++) { ans = (base*ans + (ull)s[i]) % mod1; } return ans; } ull Hash2(char s[]) //自然溢出 { ull ans = 0; int len = strlen(s); for(int i = 0;i < len;i++) { ans = (base*ans + (ull)s[i]) % mod2; } return ans; } struct Node{ ull x, y; }f[maxn]; bool cmp(Node a, Node b) { if(a.x == b.x) return a.y < b.y; return a.x < b.x; } int main() { scanf("%d", &n); for(int i = 0;i < n;i++) { scanf("%s", s); f[i].x = Hash1(s); f[i].y = Hash2(s); //printf("%lld %lld ", f[i].x, f[i].y); } sort(f, f+n, cmp); int cnt = 1; for(int i = 0;i < n-1;i++) { if(f[i+1].x != f[i].x || f[i+1].y != f[i].y) cnt++; } printf("%d ", cnt); }