字符哈希

字符串哈希实质上就是把每个不同的字符串转成不同的整数。

很明显，存储一个超长的字符串和存储一个超大但是能存的下的整数，后者所占的空间会少的多，但主要还是为了方便判断一个字符串是否出现过。

当然也很容易想到，如果有不同的字符串转成同一个整数，那么区分功能就基本废掉 ，所以我们需要一个算法把每个字符串转成唯一的整数。所以字符串哈希算法就应运而生，哈希算法的难点也就在于如何构造一个合适的Hash函数来满足我们的需求。

基本哈希方法

自然溢出hash

这种方法是利用数据结构unsigned long long的范围自然溢出：即当存储的数据大于unsigned long long的存储范围时，会自动mod \(2^{64}-1\)，就不用mod其他质数来保证唯一性了。

1
2
unsigned long long Hash[n]
hash[i]=hash[i−1]∗p+idx(s[i]);

这里的p一定要是个质数，不然可能无法保证唯一性

单哈希：

1
hash[i]=(hash[i−1])∗p+idx(s[i])%mod;

这里的p和mod都是质数，且满足p<mod。最好在选取的时候把p和mod的值取大一点。

双Hash法

双Hash就是对一个hash值用两个不同的质数进行两次mod操作，然后最后用一对数<hash1[n],hash2[n]>来表示一个字符串的哈希值，这样的一对数的重复几率加上选择较大的质数，冲突率几乎为0。

1
2
hash1[i]=(hash1[i−1])∗p+idx(s[i]) % mod1
hash2[i]=(hash2[i−1])∗p+idx(s[i]) % mod2

哈希素数的选择

61, 83, 113, 151, 211, 281, 379, 509 683, 911 / 一千以下

1217, 1627, 2179, 2909, 3881, 6907, 9209, /一万以下

12281, 16381, 21841, 29123, 38833, 51787, 69061, 92083, /十万以下

122777, 163729, 218357, 291143, 388211, 517619, 690163, 999983, /百万以下

1226959, 1635947, 2181271, 2908361, 3877817, 5170427, 6893911, 9191891, /千万以下

12255871, 16341163, 21788233, 29050993, 38734667, 51646229,68861641, 91815541,一亿以下

1e9+7 和 1e9+9 //十亿左右

122420729,163227661,217636919,290182597,386910137,515880193,687840301,917120411,/十亿以下

1222827239,1610612741, 3221225473ul, 4294967291ul /十亿以上

【模板】字符串哈希

题目描述

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

友情提醒：如果真的想好好练习哈希的话，请自觉。

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
5
6
5
abc
aaaa
abc
abcc
12345

样例输出 #1

1
4

提示

对于 \(30\%\) 的数据：\(N\leq 10\)，\(M_i≈6\)，\(Mmax\leq 15\)。

对于 \(70\%\) 的数据：\(N\leq 1000\)，\(M_i≈100\)，\(Mmax\leq 150\)。

对于 \(100\%\) 的数据：\(N\leq 10000\)，\(M_i≈1000\)，\(Mmax\leq 1500\)。

样例说明：

样例中第一个字符串(abc)和第三个字符串(abc)是一样的，所以所提供字符串的集合为{aaaa,abc,abcc,12345}，故共计4个不同的字符串。

Tip： 感兴趣的话，你们可以先看一看以下三题：

BZOJ3097：http://www.lydsy.com/JudgeOnline/problem.php?id=3097

BZOJ3098：http://www.lydsy.com/JudgeOnline/problem.php?id=3098

BZOJ3099：http://www.lydsy.com/JudgeOnline/problem.php?id=3099

如果你仔细研究过了（或者至少仔细看过AC人数的话），我想你一定会明白字符串哈希的正确姿势的_

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//map
#include<map>
#include<iostream>
#include<string>
using namespace std;
int ans, n;
map<string,int>m;

int main()
{
	cin >> n;
	string s;

	for (int i = 1; i <=n ; i++)
	{
		cin >> s;
		m[s] = 1;

	}
	cout << m.size();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//单哈希
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull base=131;
ull a[10010];
char s[10010];
int n,ans=1;
int prime=233317; 
ull mod=212370440130137957ll;
ull hashe(char s[])
{
 int len=strlen(s);
 ull ans=0;
 for (int i=0;i<len;i++)
 ans=(ans*base+(ull)s[i])%mod+prime;
 return ans;
}
int main()
{
	cin>>n;
 for(int i=1;i<=n;i++)
 {
 	cin>>s;
 	a[i]=hashe(s);
 }
 sort(a+1,a+n+1);
 for(int i=1;i<n;i++)
 {
 	if(a[i]!=a[i+1])
 	ans++;
 }
cout<<ans;
} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//双哈希
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull base=131;
struct data
{
    ull x,y;
}a[10010];
char s[10010];
int n,ans=1;
ull mod1=19260817;
ull mod2=19660813;
ull hash1(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod1;
    return ans;
}
ull hash2(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod2;
    return ans;
}
bool comp(data a,data b)
{
    return a.x<b.x;
}
main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>s;
        a[i].x=hash1(s);
        a[i].y=hash2(s);
    }
    sort(a+1,a+n+1,comp);
    for (int i=2;i<=n;i++)
        if (a[i].x!=a[i-1].x || a[i-1].y!=a[i].y)
            ans++;
    cout<<ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//大质数单哈希
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull base=131;
ull a[10010];
char s[10010];
int n,ans=1;
ull mod=212370440130137957ll;//是质数！！
ull hashs(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod;
    return ans;
}
main()
{
   	cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>s;
        a[i]=hashs(s);
    }
    sort(a+1,a+n+1);
    for (int i=2;i<=n;i++)
        if (a[i]!=a[i-1])
            ans++;
    cout<<ans;
}