哈希表

基本概念

Hash表又叫做散列表，是由 hash函数 与 链表结构 共同实现。

在散列表中，数据项被存储在一个数组中，数组的每个元素称为一个“槽”（slot）或“桶”（bucket）。哈希函数将键映射到数组的索引上，不同的键可能映射到相同的索引，这种情况称为碰撞（Collision）。

为了解决碰撞问题，通常有两种主要的方法：

拉链法（Chaining）：在碰撞发生时，将具有相同哈希值的键值对存储在同一个槽中的链表中。这样，当需要查找某个键值对时，只需遍历该槽对应的链表即可。
开放寻址法（Open Addressing）：在碰撞发生时，通过一定的方法寻找下一个可用的槽存放冲突的键值对。这可能包括线性探测、二次探测、双重散列等方法。

具体实现

通过例题来理解。

例题：模拟散列表

题目描述

维护一个集合，支持如下几种操作:

1.I x，插入一个数 x；
2.Q x，询问数 x 是否在集合中出现过；

现在要进行 $N$ 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 $N$ ，表示操作数量。

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

数据范围： $1 \leq N \leq 10^{5}, - 10^{9} \leq x \leq 10^{9}$

输出格式

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

每个结果占一行。

输入样例

5
I 1
I 2
I 3
Q 2
Q 5

输出样例

Yes
No

题目分析

大部分同学看完题后都会想到能不能用桶数组来实现呢？实际上桶数组就是一种hash。而对这道题而言，我们无法开 $10^{9}$ 这么大的桶数组，此时我们可以设计一个hash函数，将数据映射到一个比较小的值域内，同时解决映射产生的冲突即可。

常见的hash函数设计法：

取余法——H(key) = key % p，散列表长度为n，取一个<= n 的质数p
直接定址法——H(key) = key 或 H(key) = a*key + b，这种方法实际就是我们熟悉的桶数组映射方法，直接将值映射到下标，适用于数据范围较小的情况
平方取中法——取关键字的平方值中间几位作为散列地址

这里我们采用取余法来实现，而处理哈希碰撞的两种方式都进行演示。

示例代码1

开放寻址法处理哈希碰撞。

#include <cstring>
#include <iostream>

using namespace std;

//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 2e5 + 3;        //大于数据范围的第一个质数
const int null = 0x3f3f3f3f;          //规定空指针为0x3f3f3f3f

int h[N];

int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x) 
    {
        t++;
        if (t == N) t = 0;
    }
    return t;  //如果这个位置是空的, 则返回的是他应该存储的位置
}

int n;

int main() 
{
    cin >> n;
    memset(h, 0x3f, sizeof h);  //规定空指针为 0x3f3f3f3f
    while (n--) 
    {
		string op;
		int x;
		cin >> op >> x;
		if (op == "I") h[find(x)] = x;
		else 
		{
			if (h[find(x)] == null) cout << "No\n";
			else cout << "Yes\n";
		}
    }
    return 0;
}

示例代码2

拉链法处理哈希碰撞。

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 3;  // 取大于1e5的第一个质数，取质数冲突的概率最小

//* 开一个槽 h
int h[N], e[N], ne[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) {
    //用上面同样的 Hash函数 将x映射到 从 0-1e5 之间的数
    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 n;

int main() {
    cin >> n;
    memset(h, -1, sizeof h);  //将槽先清空 空指针一般用 -1 来表示
    while (n--) {
        string op;
        int x;
        cin >> op >> x;
        if (op == "I") insert(x);
        else {
            if (find(x)) cout << "Yes\n";
            else cout << "No\n";
        }
    }
    return 0;
}

例题：字符串哈希

题目描述

给定一个长度为 $n$ 的字符串，再给定 $m$ 个询问，每个询问包含四个整数 $l 1, r 1, l 2, r 2$ ，请你判断 $[l 1, r 1]$ 和 $[l 2, r 2]$ 这两个区间所包含的字符串子串是否完全相同。

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

输入格式

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

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

接下来 $m$ 行，每行包含四个整数 $l 1, r 1, l 2, r 2$ ，表示一次询问所涉及的两个区间。

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

数据范围： $1 \leq n, m \leq 10^{5}$

输出格式

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

输入样例

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例

Yes
No
Yes

题目分析

暴力做法，可以考虑用 $s u b s t r$ 获取对应区间子串，再比较是否相等， $s u b s t r$ 的时间复杂度是 $O (n)$ ，共有 $m$ 组询问，所以总时间复杂度是 $O (n m)$ ， $T L E$ 。

若可以把 $l \sim r$ 的子串映射为一个唯一的值，就可以用哈希的思想来做了，下面介绍字符串哈希算法，它可以把一个任意长度的字符串映射成一个非负整数，并且产生冲突的概率是零。

具体实现：

取一个固定值 P，把字符串看作 P 进制数，并分配一个大于 0 的数值，代表每种字符。一般来说，我们分配的数值都远小于 P，对于小写字母构成的字符串，可以令 a = 1，b = 2，... , z = 26。取一固定值 M，求出该 P 进制数对 M 的余数，作为该字符串的 Hash 值。

一般情况，取 $P = 131$ 或者 $13331$ ，此时 Hash 值产生冲突的概率极低，几乎为 $0$ 。通过映射后，只要Hash值相同，我们就可以认为字符串是相同的。通常取 $M = 2^{64}$ ，即 unsigned long long 类型直接存储 Hash 值，这么做的好处是不用处理溢出问题，产生的溢出相当于自动对 $2^{64}$ 取模，可以避免低效率的 mod 运算。

对字符串的操作，都可以直接对 $P$ 进制数进行算术运算反映到 $H a s h$ 值上。下面介绍几个重要的运算：

假设已知字符串 $S$ 的Hash值为 $H (S)$ ，在 $S$ 后加一个字符 $c$ 构成的新串 $H (S + c) = (H (S) * P + v a l u e [c])$ $m o d$ $M$ 。乘 $P$ 表示 $P$ 进制左移一位， $v a l u e [c]$ 是字符 $c$ 表示的数值。

如果已知 $S$ 的Hash值 $H (S)$ ，字符串 $S + T$ 的 $H a s h$ 值 $H (S + T)$ ，那么字符串 $T$ 的 $H a s h$ 值 $H (T) = (H (S + T) - H (S) * P^{l e n (T)})$ $m o d$ $M$ 。怎么理解呢？这就相当于通过 $P$ 进制下在 $S$ 后面补 $0$ 的方式，把 $S$ 左移到与 $S + T$ 左端对齐，然后二者相减就得到了 $H (T)$ 。

例如： $S =$ "abc"， $c =$ "d"， $T =$ "xyz"，则：

操作一

$S$ 表示 $P$ 进制数 1 2 3

$H (S) = 1 * P^{2} + 2 * P^{1} + 3 * P^{0}$

$H (S + c) = H (S) * P + 4$

操作二

$S + T$ 表示 $P$ 进制数：1 2 3 24 25 26

$H (S + T) = 1 * P^{5} + 2 * P^{4} + 3 * P^{3} + 24 * P^{2} + 25 * P + 26$

$H (S) * P^{l e n (T)} = (1 * P^{2} + 2 * P^{1} + 3 * P^{0}) * P^{3} = 1 * P^{5} + 2 * P^{4} + 3 * P^{3}$

$H (T) = H (S + T) - H (S) * P^{l e n (T)} = 24 * P^{2} + 25 * P + 26$

有了上面的操作，我们可以在 $O (N)$ 时间内预处理字符串所有前缀的 $H a s h$ 值，并在 $O (1)$ 的时间查询任意子串的 $H a s h$ 值。

示例代码

#include <iostream>
#include <algorithm>

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)) puts("Yes");
        else puts("No");
    }
    return 0;
}