【字符串哈希（8848,两个密码雾）+哈希表】

哈希（hash）

　　对于我来说，HASH就像一个加密软件，你输入一个值，他就会输出值，并且比之前的值更优，更方便。而这个值呢，就叫做哈希值。然后字符串哈希就是输入一个字符串，把它转成对应的HASH值就行了。

　　对于每个字符串，我们通过一个固定的转换方式，使相同字符串的哈希值一定相同，不同字符串的值尽量不同。因为很可能存在两个不同的字符串哈希值一样的操作，我们称之为“哈希冲突”。

　　我们此处传换的方式，就是最常见的进制哈希，它的核心是给出一个固定进制base，把字符串上面的每一个元素看成base进制的每一个数字，然后转换成十进制，最后的结果就是HASH值。最后我们只需要比较每一个字符串的HASH值就可以知道他们是不是同一个字符串。

　　关于进制的选择，还是很自由的，但是一定不要含有mod的质因子（那你还模什么模），所以我们取进制和mod时，一般都是质数。但是简单的还是利用unsigned long long，不手动进行取模，它溢出时会自动对 $2^{6} 4$

　　下面我利用【模板】字符串哈希给大家介绍一下这两种进制哈希：

题目描述

　　如题，给定N个字符串（第i个字符串长度为Mi，字符串内包含数字、大小写字母，大小写敏感），请求出N个字符串中共有多少个不同的字符串。

输入输出格式

输入格式：

　　第一行包含一个整数N，为字符串的个数。

　　接下来N行每行包含一个字符串，为所提供的字符串。

输出格式：

　　输出包含一行，包含一个整数，为不同的字符串个数。

输入样例1

5
abc
aaaa
abc
abcc
12345

输出样例1

1、自然溢出哈希

对于这个哈希，我们不对它取模，而是利用unsigned long long的溢出取模。　　　

 1 #include<bits/stdc++.h>
 2 #define FAST std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
 3 using namespace std;
 4 typedef unsigned long long ull;//typedef专门把C++的值的类型改名字，和宏定义一个道理，如自带的int，char或者自定义的struct 
 5 int n,ans=1;//种类因为不搜第一个，所以初值是一 
 6 ull base=131;//进制数 
 7 int a[10001];//记录hash值 
 8 int hash(string s)
 9 {
10     ull sum=0;//哈希值
11     for(int i=0;i<s.size();i++)
12     {
13         sum=sum*base+(ull)(s[i]);//乘进制数加上这一位 
14     }
15     return sum;//返回hash值 
16 }
17 int main()
18 {
19     FAST;//优化输入输出 
20     cin>>n;
21     for(int i=1;i<=n;i++)
22     {
23         string s;//输入字符串 
24         cin>>s;
25         a[i]=hash(s);//给它hash值 
26     }
27     sort(a+1,a+1+n);//hash值排序 
28     for(int i=2;i<=n;i++)
29     {
30         if(a[i]!=a[i-1])ans++;//不一样种类就加一 
31     }
32     cout<<ans;
33 }

2、单哈希

自定义取模的值就行了。

 1 #include<bits/stdc++.h>
 2 #define FAST std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
 3 using namespace std;
 4 int mod=20160817;//神奇的数字（质数）但是交上去只能得80分，所以我们用一个大一点的质数（212370440130137957ll） 不要在意后面的两个符号，交上去就对了 
 5 int n,ans=1;
 6 long long base=131;
 7 int a[100001];
 8 int hash(string s)
 9 {
10     int sum=0;//哈希值
11     for(int i=0;i<s.size();i++)
12     {
13         sum=sum*base+(int)(s[i]);//乘进制数加上这一位 
14         sum%=mod;//模一下 
15     }
16     return sum;//返回hash值 
17 }
18 int main()
19 {
20     FAST;//优化输入输出 
21     cin>>n;
22     for(int i=1;i<=n;i++)
23     {
24         string s;//输入字符串 
25         cin>>s;
26         a[i]=hash(s);//给它hash值 
27     }
28     sort(a+1,a+1+n);//hash值排序 
29     for(int i=2;i<=n;i++)
30     {
31         if(a[i]!=a[i-1])ans++;//不一样种类就加一 
32     }
33     cout<<ans;
34 }

很显然，大家看到上面的代码，还是有可能出现哈希冲突的情况，针对这种情况，我们要不就把模的数再大一点，要不就换种方式，来解决。

3、多重哈希

这其实就是你用不同的两种或多种方式哈希，然后分别比对每一种哈希值是否相同——显然是增加了空间和时间，但也确实增加了其正确性。

 1 #include<bits/stdc++.h>
 2 #define FAST std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
 3 using namespace std;
 4 int mod1=20160817;
 5 int mod2=19260817; 
 6 int n,ans=1;
 7 int base=131;
 8 struct node{
 9     int x,y;
10 }a[100001];
11 int hash1(string s)
12 {
13     int sum=0;
14     for(int i=0;i<s.size();i++)
15     {
16         sum=base*sum+(int)(s[i]);
17         sum%=mod1;
18     }
19     return sum;
20 }
21 int hash2(string s)
22 {
23     int sum=0;
24     for(int i=0;i<s.size();i++)
25     {
26         sum=base*sum+(int)(s[i]);
27         sum%=mod2;
28     }
29     return sum;//返回hash值 
30 }
31 bool sj(node x,node y)
32 {
33     return x.x<y.x;
34 }
35 int main()
36 {
37     FAST;//优化输入输出 
38     cin>>n;
39     for(int i=1;i<=n;i++)
40     {
41         string s;//输入字符串 
42         cin>>s;
43         a[i].x=hash1(s);//给它hash值 
44         a[i].y=hash2(s);
45     }
46     sort(a+1,a+1+n,sj);//hash值排序 
47     for(int i=2;i<=n;i++)
48     {
49         if(a[i].x!=a[i-1].x||a[i].y!=a[i-1].y)ans++;
50     }
51     cout<<ans;
52 }

哈希表

说到底，我们哈希还是来分辨字符串的。有人说：字符串不可以用map吗？

可以的，但是你要知道，map是O（n）的，而哈希只需要计算一下，就直接找到，O（1）的，所以明白了吗？

这就是hash_map，也叫哈希表

哈希表呢，就是开一串数组，然后每一个字符串对应一个下标，而这个下标，就是他的哈希值（因为这里的数组开不了很大，所以一般不用自然溢出）

所以就存在哈希值重复的情况，我们这里有三种操作方式

开链法（链式前向星）

当哈希值冲突的时候，我们就可以用链式前向星（就和那个存图一样的）

void add(int x)
{
    cnt++;
    int key=x%mod;
    sum[cnt].pre=last[key];
    last[key]=cnt;
    sum[cnt].x=x;
}

这里的key是哈希值，last[i]是最后一个哈希值为i的编号，然后pre就是上一个，连起来就行了。查找的时候就像基本的前向星一样查找就是了，一个一个向上遍历

这里要提醒一下，当你的mod大，数组就大，空间就大，相应的冲突就小，所以时间就比较快。而mod小了，数组就小，空间小，相应的冲突大，所以时间就会慢，有的时候会超时。

线性勘测法

这里的线性勘测法就是有冲突的，下标就加一，如果还有，就继续加一......

1 void add(int x)
2 {
3     int key=x%mod;
4     while(sum[key].x&&sum[key].x!=x)key=(key+1)%mod;
5     sum[key].x=x;
6     return ;
7 }

找的时候一样

bool find(int x)
{
    int key=x%mod;
    while(sum[key].x&&sum[key].x!=x)key=(key+1)%mod;
    if(!sum[key].x)return false;
    return true;
}

所以这个时间复杂度还是很麻烦的，因为你会发现元素都是堆在一堆的，查找很慢，所以我们要跳来跳去

二次勘测法

这个用的就是平方跳跳跳，1^2,-1^2,2^2.......（S是平方数组）

void add(int x)
{
    int key=x%mod;
    int i=1;
    while(sum[key].x&&sum[key].x!=x)
    {
        key=((key+S[i])%mod+mod)%mod;
        i++;
    }
    sum[key].x=x;
}

 1 bool find(int x)
 2 {
 3     int key=x%mod;
 4     int i=1;
 5     while(sum[key].x&&sum[key].x!=x)
 6     {
 7         key=((key+S[i])%mod+mod)%mod;
 8         i++;
 9     }
10     if(!sum[key].x)return false;
11     return true;
12 }

因为这种方法存在一直在跳循环，所以数组空间最好开大点......

【字符串哈希（8848,两个密码 雾）+哈希表】