哈希表

哈希表的作用

将一个庞大的空间（值域）映射到比较小的空间（0-N），N一般为1e5-1e6左右。

这种映射通常使用模运算来进行，但将若干较大范围的数映射到较小范围的数，难免会发生冲突（两个数映射到同一个数上），为解决这种冲突，我们需要特殊的存储结构。

存储结构

哈希表的存储结构有两种：拉链法和开放寻址法，这两者使用不同的方式处理冲突。

拉链法

通过一个一维数组（0-N）来存储映射后的数，我们可以把这个数组看为一个个槽，当发生冲突时，我们会将该槽下拉一条链表，用链表存储映射到同一个槽的数据。

因此，这里我们要用到单链表的知识，将每个h[k]set为-1，表示槽指向尾节点。

插入

在插入时，我们要用到单链表的头插法。

void insert(int x)
{
	int k = (x % N + N) % N; // 避免出现模为负
    e[idx] = x;
    ne[idx] = h[k];
    h[x] = 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;
}

开放寻址法

开放寻址法不需要用到链表，只需要开一个一维数组，因此结构上看起来会更简单，但长度会更长一些（2N~3N），以此降低冲突的概率。

我们该如何处理冲突呢？对于开放寻址法，我们从前往后从h[k]开始往后寻找，如果h[k]不为空，就再往后一位寻找，直到为空为止。

find操作

开放寻址法的核心是find操作

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;
}

return k 的作用可以集查找和插入为一体，当h[k]为null时，代表为空，则会返回应插入的位置。若h[k]为x时，则代表找到x在哈希表中的位置。

有了find操作，插入和查找就变得十分简单了。

插入

int k = find(x);
h[k] = x;

查询

if (h[k] != null) puts("Yes");
else puts("No");

开放寻址法完整代码

#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()
{
    memset(h, 0x3f, sizeof(h));

    int n;
    scanf("%d", &n);

    while (n -- ){
        char op[2];
        int x;
        scanf("%s %d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else{
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }   
    return 0;
}

字符串哈希

字符串哈希的实质是将不同的字符串转换为不同的整数，并且为了更方便地判断一个字符串是否出现过，仅需要O(1)的时间。

要将字符串转换为整数，我们首先要预处理出所有前缀子串的哈希值。那么如何来定义前缀的哈希值呢？

我们通常将一个字符串看为一个P进制的数，一位字符看为一位数字。例如”ABCD”这个字符串，则可以把A当作1，B当作2，C当作3…..那么这个P进制数对应的十进制数就是1 * p^3 + 2 * p^2 + 3 * p^1 + 4 *p^0，当字符串很长时，这个十进制数会非常大，我们需要再将转化后的P进制数模上Q，以此将字符串映射为0~Q-1的数。

其中，我们需要注意不能将字符映射为0，若一个字符串“A”的哈希值为0，“AA”也为0，“AAA”同样为0，这样就会出现冲突。

当P足够好是，可以避免大部分冲突，经验之谈，当P为131或13331时， Q为2^64足够好，在大多数情况下不会出现冲突。

有了前缀的字符串哈希值，我们该如何求一个区间的字符串的哈希值呢？以字符串“ABCDEFG”为例子，令A为1，B为2，以此类推，

字符串“ABCD”的哈希值为1 * p^3 + 2 * p^2 + 3 * p^1 + 4 *p^0，而原字符串的哈希值为1 * p^6 + 2 * p^5 + 3 * p^4 + 4 * p^3 + 5 * p^2 + 6 * p^1 + 7 * p^0，若要求出字串“EFG”的哈希值，只需求出5 * p^2 + 6 * p^1 + 7 * p^0即可，通过这样表示，我们可以很清晰地看出，只需令“ABCD”的哈希值乘上一个p^3，再与原串的哈希值相减即可。

由此我们得到字串哈希值的推导公式

h[r] - h[l - 1] * p^(r - l + 1);

还记得我们前文提到的Q吗，如果我们直接使用unsigned long long 来存储所有的h，我们就不需要再进行取模操作，令其自然溢出，即相当于取2^64的模。

字符串哈希完整代码

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

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

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s", str + 1);

    p[0] = 1;
    for (int i = 1; i <= n; i ++ ){
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }

    while (m -- ){
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

        if (get(l1, r1) == get(l2, r2)) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}