hash是一门优雅的暴力

关于字符串hash，就一句话：

把字符串有效地转化为一个整数

在计算机里，用的是二进制编码。在很多语言里，都是用数字作为数组的下标。因为用数字来存储、表达一个object非常方便。

如果能有一种算法，把每个字符串有效地、”唯一”的映射到每个“不同”的整数，我们就能很好的处理字符串。

hash的思想是挺好理解的，那么hash的算法应该怎么去写？

不建议写自然溢出的hash算法，因为新的字符串的题目出题人都喜欢卡这个

单hash：

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string.h>
 5 #include <stdlib.h>
 6 #include <math.h>
 7 #include <queue>
 8 #include <set>
 9 
10 #define INF 0x3f3f3f3f
11 #define pii pair<int,int>
12 #define LL long long
13 using namespace std;
14 typedef unsigned long long ull;
15 const int maxn = 2e6+6;
16 
17 
18 int a[maxn];
19 char s[maxn];
20 
21 
22 ull base = 131;
23 ull mod = 1e9+7;
24 ull p[maxn],h[maxn];
25 void Hash(char s[]){
26     int n = strlen(s);
27     p[0] = 1;
28     for (int i=1;i<=n;i++){
29         p[i] = p[i-1] * base % mod;
30     }
31     for (int i=1;i<=n;i++){
32         h[i] = (h[i-1]*base %mod + s[i])%mod;
33     }
34 }
35 ull get(int l,int r){
36     return (h[r] - h[l-1]*p[r-l+1] % mod + mod)%mod;
37 }
38 
39 int main(){
40     int n;
41     int ans = 1;
42     scanf("%d",&n);
43     for (int i=1;i<=n;i++){
44         scanf("%s",s+1);
45         int len = strlen(s+1);
46         //cout << len << endl;
47         Hash(s+1);
48         a[i] = h[len];
49     }
50     sort(a+1,a+1+n);
51     for (int i=2;i<=n;i++){
52         if (a[i]!=a[i-1])
53             ans++;
54     }
55     printf("%d\n",ans);
56     return 0;
57 }

双hash：

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string.h>
 5 #include <stdlib.h>
 6 #include <math.h>
 7 #include <queue>
 8 #include <set>
 9 
10 #define INF 0x3f3f3f3f
11 #define pii pair<int,int>
12 #define LL long long
13 using namespace std;
14 typedef unsigned long long ull;
15 const int maxn = 2e6+6;
16 
17 struct Node{
18     int x,y;
19 }a[maxn];
20 
21 char s[maxn];
22 
23 
24 ull base = 131;
25 ull mod1 = 1e9+7;
26 ull mod2 = 1e9+9;
27 ull p[maxn],h[maxn];
28 bool cmp(Node a,Node b){
29     return a.x<b.x;
30 }
31 void Hash1(char s[]){
32     int n = strlen(s);
33     p[0] = 1;
34     for (int i=1;i<=n;i++){
35         p[i] = p[i-1] * base % mod1;
36     }
37     for (int i=1;i<=n;i++){
38         h[i] = (h[i-1]*base % mod1 + s[i]) % mod1;
39     }
40 }
41 
42 void Hash2(char s[]){
43     int n = strlen(s);
44     p[0] = 1;
45     for (int i=1;i<=n;i++){
46         p[i] = p[i-1] * base % mod2;
47     }
48     for (int i=1;i<=n;i++){
49         h[i] = (h[i-1]*base % mod2 + s[i]) % mod2;
50     }
51 }
52 
53 int get1(int l,int r){
54     return (h[r] - h[l-1]*p[r-l+1] % mod1 + mod1 ) % mod1;
55 }
56 
57 int get2(int l,int r){
58     return (h[r] - h[l-1]*p[r-l+1] % mod2 + mod2 ) % mod2;
59 }
60 
61 int main(){
62     int n;
63     int ans = 1;
64     scanf("%d",&n);
65     for (int i=1;i<=n;i++){
66         scanf("%s",s+1);
67         int len = strlen(s+1);
68         //cout << len << endl;
69         Hash1(s+1);
70         a[i].x = h[len];
71         Hash2(s+1);
72         a[i].y = h[len];
73     }
74     sort(a+1,a+1+n,cmp);
75     for (int i=2;i<=n;i++){
76         if (a[i].x!=a[i-1].x ||a[i].y!=a[i-1].y)
77             ans++;
78     }
79     printf("%d\n",ans);
80     return 0;
81 }