哈希表

适合将定义域很大的数据映射到值域较小的集合。是一般意义上的哈希，离散化是一种特殊的哈希，需要保序，哈希函数需要单调递增。

x∈(10−9,109),h(x)∈(0,105)x\in(10^{-9}, 10^{9}), h(x)\in(0, 10^{5})

哈希函数一般为：h(x)=x \mod 质数

质数应尽可能离 2n2^{n} 要远，这样冲突的概率最小。

存储结构

开放寻址法

只使用一个一维数组，经验值开辟 2~3 倍元素个数的数组空间。

拉链法

开一个一维数组，长度为值域大小。每次算出一个哈希值 h[x] = y，就在 y 的位置上开一个链表，在链表末尾记录 x 的值。

查询某个数 x 是否在哈希表中，首先计算出哈希值 h[x] = y，然后遍历哈希值对应的数组位置 y 上的链表，查看链表中是否存在 x。

总结：一个数组，拉了很多链表。数组插槽编号对应的是哈希值，数组插槽内容对应的是链表节点编号。链表节点中存的是原始数据值。

字符串哈希方式

将字符串看成一个 p 进制数。

例如：“ABCD”

hash((ABCD)p)=(1∗p3+2∗p2+3∗p1+4∗p0)mod  Qhash((A B C D)_p) = (1 * p^{3} + 2 * p^{2} + 3 * p^{1} + 4 * p^{0}) \mod Q

p 取 131 或 13331。

Q 取 2642^{64}。

实际写代码时，A B C D 取他们的 ascii 码就可以，不必写成上面的 1 2 3 4。

这样可以在 99% 的情况下避免冲突。

注意：

  1. 不能把某个字母映射成 0。
  2. 不考虑冲突。

例题

模拟散列表

拉链法

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
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100003;
// 哈希数组、链表
int h[N], e[N], ne[N], idx;

// 哈希数组每个位置是一个插槽，存储的值是一个链表节点的标号
void insert(int x) {
    // 在 C++ 中负数取模的结果是负数，为保证哈希之后是正数，需要对取模结果加 N 再模 N
    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]) {
        if(e[i] == x) return true;
    }
    return false;
}
int main () {
    int n;
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    while(n--) {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if(*op == 'I') {
            insert(x);
        } else {
            if(find(x)) 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
36
37
38
39
#include <iostream>
#include <cstring>
using namespace std;

// 选取一个 null 标记，如果 find(x) == null，说明哈希表中不存在 x 元素。这个标记应该选取在数据范围之外。
const int N = 200003, null = 0x3f3f3f3f;
int h[N];

int find(int x) {
    // 按照哈希函数给 x 找一个坑位
    int k = (x%N+N)%N;
    // 如果坑位被占，且元素不是 x，就尝试下一个坑位
    while(h[k] != null && h[k] !=x) {
        k++;
        // 如果 k 走到头了就从 0 开始
        if(k==N) k=0;
    }
    return k;
}

int main() {
    int n;
    scanf("%d", &n);
    // memset 按照字节设置内存中的内容，int 数据为 4 字节，因此每个数就是 0x3f3f3f3f
    memset(h, 0x3f, sizeof h);
    while(n--) {
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        int k = find(x);
        if(*op == 'I') h[k] = x;
        else {
            if(h[k] != null) 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
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
using namespace std;

const int N = 100010, P = 131;

typedef unsigned long long ULL;

int n, m;
char str[N];
// p[i] 表示 P 的 i 次幂
ULL h[N], p[N];

// 计算公式，预处理字符串所有前缀哈希值后，可以算出任意子串的哈希值
/*
高位                        低位
A  B  C  D  E  F  G  H  I  J
     l-1 l        r
----------------------------->
0  1  2  3  4  5  6  7  8  9
已知：
h[l-1] = hash("ABC")
h[r] = hash("ABCDEFG")
求：hash("DEFG")

将 h[l-1] 与 h[r] 对齐，即 "ABC" 与 "ABCDEFG" 高位对齐。为此需要将 h[l-1] 向左平移位数之差 r - l + 1 个位置。
所以计算 l~r 子串字符串哈希公式为：hash(l, r) = h[r] - h[l-1] * p[r - l + 1]

*/
ULL get(int l, int r) {
    return h[r] - h[l-1]*p[r-l+1];
}

int main() {
    scanf("%d%d%s", &n, &m, str + 1);
    p[0] = 1;
    for(int i=1;i<=n;i++) {
        p[i] = p[i-1] * P;
        h[i] = h[i-1] * P + str[i];
    }
    while(m--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if(get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}