带你手撕哈希（hash）表【数组】

思维导图

哈希

哈希的本质是映射，把一个较大范围的数据映射到一个较小的数据里面，从而更方便的进行某些操作。

哈希函数

通过某种函数关系，将一堆较大范围的数据映射成较小范围的数据，这样的函数关系就叫做哈希函数，比如我们设较大范围的数据为x，较小范围的数据为y，常用的函数为 y = x % mod。

哈希冲突

我们把一个很大范围的数据映射到一个较小范围的数据中，则必然存在至少两个x被映射被映射到同一个y中，这便是哈希冲突,如何尽可能的规避哈希冲突是哈希问题的一个很重要的问题。

散列表

我们先引入一个例题。

拉链法

所谓拉链法便是将x通过y = x % mod找到对应的y，从而在y的下面拉一条链子，注意每次拉链是在y头拉。

时间复杂度：因为通常我们这个链子也不会很长，基本是1到3个，这相对于1e5来说近似o（1）。

#include<bits/stdc++.h>

using namespace std;

const int N = 100003;//取质数从数学的角度来说可以最大程度的避免哈希冲突

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

void insert(int x){
    int k = (x % N + N) % N;//哈希函数
    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]){//遍历
        int j = e[i];
        if(j == x) return true;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(h, -1, sizeof h);
    int n;
    cin >> n;
    while(n --){
        char op;
        cin >> op;
        if(op == 'I'){
            int x;
            cin >> x;
            insert(x);
        }else{
            int x;
            cin >> x;
            if(find(x)) cout << "Yes" << "\n";
            else cout << "No" << "\n";
        }
    }
    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

我们可以把这个看成一个图，也可以开一个二维数组存。

#include<bits/stdc++.h>

using namespace std;

const int N = 100003;

vector<vector<int>> e(N);

void insert(int x){
    int k = (x % N + N) % N;
    e[k].push_back(x);
} 

bool find(int x){
    int k = (x % N + N) % N;
    for(auto i : e[k]){
        if(i == x) return true;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    while(n --){
        char op;
        cin >> op;
        if(op == 'I'){
            int x;
            cin >> x;
            insert(x);
        }else{
            int x;
            cin >> x;
            if(find(x)) cout << "Yes" << "\n";
            else cout << "No" << "\n";
        }
    }
    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

开放寻址法

开放寻址法俗称蹲坑法，假如我们要映射到1e5,这时我们需要开一个比这个数据范围更大一点约为2到3倍的数组，然后通过y = x % mod,找到y，看看y这个坑位里面有没有人，没人我就蹲，有人我就找下一个。

#include<bits/stdc++.h>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];

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(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(h, 0x3f, sizeof h);
    int n;
    cin >> n;
    while(n --){
        char op; 
        int x;
        cin >> op >> x;
        if(op == 'I'){
            int k = find(x);
            h[k] = x;
        }else{
            int k = find(x);
            if(h[k] != null) cout << "Yes" << "\n";
            else{
                cout << "No" << "\n";
            }
        }
    }
    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

字符串哈希

我们这里用的字符串哈希方法是字符串前缀哈希方法。

h函数存的值为前几个字母所映射的哈希值，而怎么把字符串转化为哈希值呢，我们这里采用一个奇妙的办法——进制。

通过这种方式， 我们就非常神奇的将每一个前缀字符串存到h数组了。

但还有两个问题，p和q应该取啥呢，从数学上讲，当p取131或者13331，q取2的64次方，这时可以最大程度的避免哈希冲突，然后我们这里用到一个技巧，我们在设h数组就把数组类型设成unsigned long long（范围为0 到 2的64次方 - 1）,这样根据一点机组的知识，编译器就会自动帮我们取模了。

接下来我们引入一个例题。

我们先给出AC代码，再逐步讲解：

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
const int N = 1e5 + 10, P = 131;

int n, m;
char s[N];
ull h[N], p[N];

ull get(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];//区间公式
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s+1;
    p[0] = 1;
    for(int i = 1;i <= n;i ++){
        p[i] = p[i - 1] * P;//进制
        h[i] = h[i - 1] * P + s[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;
}
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

首先我们先介绍这个前缀和公式：

用这种方式我们就可以完美表示前缀字符串的哈希值。
接下来就是求区间（子串）了

这样我们就可以求区间了。
这道题的整个时间复杂度为o(n) + o(m)(每次查询时的时间复杂度是近似O（1）的时间复杂度。