1.哈希表的两种写法

2.字符串的哈希方法

哈希表的两种写法

具体内容点击查看

模拟散列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
维护一个集合，支持如下几种操作：

I x，插入一个数 x；
Q x，询问数 x 是否在集合中出现过；
现在要进行 N 次操作，对于每个询问操作输出对应的结果。

输入格式
第一行包含整数 N，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围
1≤N≤105
−109≤x≤109
取mod的值

h(k) = k mod m

哈希的时候取mod的数一般取成质数，并且要离2的整次幂尽可能远。这样冲突的概率是最小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int main(){
    for(int i = 1e5;; i++){
        bool isFlag = 1;
        for(int j = 2; j * j <= i; j++){
            if(i % j == 0){
                isFlag = 0;
                break;
            }
        }
        if(isFlag) {
            cout<<i<<endl;
            return 0;
        }
    }
}
//100003
//所以最好mod100003

拉链法

点击查看

拉链法就是在数组上开槽，上面接链表，用来存冲突的数

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
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 3;

int h[N], e[N], ne[N], idx;

void insert (int x){
    int k = (x % N + N) % N;//加N然后modN是为了让x%N的值变为整数。k就是hash值
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++;
}

bool find(int x){
    int k = (x % N + N) % N;
    for(int i = h[k]; i != -1; i = ne[i])
        if(e[i] == x)
            return true;
    return false;
}

int main(){
    int n;
    scanf("%d", &n);
    
    memset(h, -1, sizeof h);//链表中空指针一般用-1来表示
    
    char op;
    int x;
    while(n--){
        cin>>op>>x;
        if(op == 'I')insert(x);
    	else {
            if(find(x)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

开放寻址法

点击查看
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
//只开了一个一维数组
//数组长度要开到题目要求的2~3倍
//思路：h[x] = k，如果有值，就看下一个位置，直到找到空位将x填进去。
#include <iostream>
#include <cstring>
using namespace std;
//先约定一个数，如果数组中某个位置上是这个数，则说明这个位置上没有人
//约定数要在数据范围之外
//常采用0x3f3f3f3f来作为无穷大。0x3f3f3f3f主要有如下好处：
//0x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即10^9数量级，而一般场合下的数据都是小于10^9的。
//0x3f3f3f3f * 2 = 2122219134，无穷大相加依然不会溢出。
//可以使用memset(array, 0x3f, sizeof(array))来为数组设初值为0x3f3f3f3f，因为这个数的每个字节都是0x3f。
const int N = 2e5 + 3, null = 0x3f3f3f3f;

int h[N];
//开放寻址法的核心：find函数
//如果x在哈希表中已经存在，返回x的位置；如果x在哈希表中不存在，则返回x应该存储的位置
int find(int x){
    int k = (x % N + N) % N;
    
    while(h[k] != null && h[k] != x){
        k++;
        if(k == N) k = 0;
    }
    return k;
}

int main(){
    int n;
    cin>>n;
    
    memset(h, 0x3f, sizeof h);
    
    char op;
    int x;
    while(n--){
        cin>>op>>x;
        if(op == 'I'){
            h[find(x)] = x;
        }
        else{
            if(h[find(x)] != null) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

字符串的哈希方法

字符串前缀哈希法

字符串前缀哈希法很好，当我们需要判断两个字符串是不是相等的时候就可以用这个方法

字符串哈希法除了无法处理循环节的问题，其他kmp能做的，字符串哈希都能做

s1:预处理所有前缀的哈希

h[i] = h[i - 1] * p + str[i]

s2:

  1. 先将字符串看成一个p进制的数，有几个字符就是几位
  2. 把p进制的数转化成10进制的数，每一位上的数乘以p的相应次幂
  3. 最后mod一个数q，就成功将任意一个字符串映射成0~q-1之间的一个数

注意：①不能映射成0

​ ②这个方法不考虑冲突，经验值：p = 131或13331；用这个值99999%不会产生冲突

​ q = 2^64（用unsigned long long 来存储h[]，相当于取mod 2^64，因 为超出范围会溢出）

s3:利用所有前缀的哈希值，可以求出字符串中所有子串的哈希值

例：已知h[R],h[L],求字符串L到R的哈希值？

利用这个公式 h[R] - h[L-1] * p^(R-L+1) 即可求得子串的哈希值

例题：字符串哈希
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式
第一行包含整数 n 和 m，表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 1 开始编号。

输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围
1≤n,m≤105
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 <iostream>

using namespace std;

typedef unsigned long long ULL;//使用ULL，自动取模

const int N = 1e5 + 10, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];//p数组用来处理P的R-L+1次方;h数组是前缀的哈希值

ULL get(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];//套公式，求得子串的哈希值
}

int main(){
    cin>>n>>m>>str + 1;
    
    p[0] = 1;
    for(int i = 1; i <= n; i++){
        p[i] = p[i - 1] * P;			 //预处理P的次幂
        h[i] = h[i - 1] * P + str[i];//预处理所有前缀的哈希
    }
    
    while(m--){
        int l1, r1, l2, r2;
        cin>>l1>>r1>>l2>>r2;
        if(get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
	return 0;
}