洛谷深基hash表
字符串哈希
给定 N 个字符串（第 i个字符串长度为 Mi，字符串内包含数字、大小写字母，大小写敏感），请求出 N 个字符串中共有多少个不同的字符串。
我们不妨先分析简化版的问题：
给定N个自然数，值域为[0,109]，求出N个自然数中共有多少个不同的自然数
如果值域为[0,107]，可以利用计数排序，定义数组a[1e7]，出现就++，最后统计有多少非0
当值域拓展到[0,109]，可以取一个mod，定义一个大小为mod的数组，然后把每个数对mod取模，如果两个数取mod之后值相同，就默认为两个数相同
#include <bits/stdc++.h>
#define mod 233333
using namespace std;
int n,x,ans,a[mod+5];
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
x%=mod;
if(!a[x]) a[x]=1,ans++;
}
cout<<ans<<endl;
return 0;
}
但是如果有两个数对mod取模之后恰好得到了相同的结果，那么就会起冲突
优化：
把一个int的数组改成一个vector
然后每次判断一个属x是否存在的时候，遍历x%mod位置的vector或者链表中所有元素，看是否有x即可
#include <bits/stdc++.h>
#define mod 233333
using namespace std;
int n,x,ans;
vector<int> linker[mod+2];
inline void insert(int x){
for(int i=0;i<linker[x%mod].size();i++){
if(linker[x%mod][i]==x)
return ;
}
linker[x%mod].push_back(X);
ans++;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
insert(x);
}
cout<<ans<<endl;
return 0;
}
举例：当要存储的数字为1 2 3 4 5 6，模数为4的时候,vector内是这样的
0 1 2 3
4 1 2 3
5 6
当新加入233时，233mod4=1，遍历1的vector，发现里面没有233，就将233push_back到1的vector后面
0 1 2 3
4 1 2 3
5 6
233
这样的数据结构就是哈希表，hash表
好，那么前面都是对于数字的处理，那么我们如何将字符串转换为数字呢？
通过ASCII码的原理，我们可以将单个字符映射为一个数字。
我们将字符序列映射成0到mod-1中的一个数字，称为字符串的hash值
\(hash=(hash*k+s[i])\%mod\)
一般来说mod会取一个比较大的质数来避免冲突
那么我们回到原题，由于可能有多个不同的字符串对应同一个hash值，对于每个hash建立一个vector用来存每个hash的所有字符串，每次将插入的字符串呵hash值相同的字符串进行比较，看是否相等，就可以知道是否出现过了
#niclude <bits/stdc++.h>
#define maxn 1510
#define base 261
#define mod 23333
using namespace std;
int n,ans;
char s[maxn];
vector<string> linker[mod+2];
inline void insert(){
int hash=1;
for(int i=0;s[i];i++)
hash=(hash*111*base+s[i])%mod;
string t=s;
for(int i=0;i<linker[hash].size();i++){
if(linker[hash][i]==t)
return ;
}
linker[hash].push_back(t);
ans++;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>s;
insert();
}
cout<<ans<<endl;
return 0;
}