哈希表 | 学习笔记

哈希表

基本思想：

将大范围的复杂数据按照一个固定操作 $h(x)$ 映射到小范围的简单数据，例如 $h(x) = x \mod 10^5 + 3$

而此时我们发现，$h(2)$ 与 $h(1e5 + 5)$ 均会映射到同一个点 2，那么如何处理这种冲突呢？

注：为保证冲突概率最小，被模数要取为质数 ($10^5 + 3$) 且尽可能远离 $2$ 的正数次幂

拉链法 和 开放寻址法

在下面的讲解中，我们将 $10^{-9}$ \sim $10^9$ 范围的数据使用 $h(x) = x \mod 1e5 + 3$ 操作映射为 $0 \sim 10^5 - 1$

拉链法：

顾名思义，即在存储哈希值的一维数组的每一个点下拉一条单链表，插入元素时在链下新建一个节点，查找元素时遍历该链表即可

int h[N];
// 哈希数组
int e[N], nxt[N], idx;
// 链表

插入操作：

void insert(int x) {
// 链表头插法 
	int k = (x % N + N) % N;
	// 将所有数映射到 0 ~ N，保证取得正数 
	e[idx] = x;
	nxt[idx] = h[k];
	h[k] = idx ++;
    // 插入元素
}

查找元素：

bool find(int x) {
// 遍历链表
	int k = (x % N + N) % N;
	for (int i = h[k]; i != -1; i = nxt[i])
		if (e[i] == x) return true; // find
	return false; 
}

开放寻址法

基本思路：
对于 x 进行操作 h(x)，如果哈希表中 h(x) 的位置已经有数，那么向后找，直到找到一个空位置，将 x 插入。查找时同理

注意 ：开放寻址法的哈希表数组需要将常数扩大 2 ~ 3倍

查找元素：

int find(int x) {
	int k = (x % N + N) % N;
	while (h[k] != NULLX && h[k] != x) {
		k ++;
		if (k == N) k = 0;
	}
	return k;
}

插入：

h[find(x)] = x;

---

字符串哈希：

1. 将每一个字母映射为一个 $P$ 进制的数，整个字符串即可用一个多位的 $P$ 进制数表示。例如对于字符串$ABCDABDEF$：

   h[0] = $0$
   h[1] = “$A$” 的哈希值
   h[2] = “$AB$” 的哈希值
   …………

注意：不能将字母映射为 $0$，该位数字无意义会导致不同字符串映射为同一个数

2. 将这个 $P$ 进制的数转化为 $10$ 进制储存，将每一位 $i$ 的前缀存入哈希数组 $h_i$ 中

$h_1 = 1;$
$h_2 = 1 \times p^1 + 2 \times p^0$
$h_3 = 1 \times p^2 + 2 \times p^1 + 3 \times p^0$
…………

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

3. 因为字符串位数可能很多导致转化的 $10$ 进制数极大，可以在运算过程中对一个常数 $Q$ 取模

通过以上三个步骤，我们即可将任何一个字符串映射到从 $0 \sim Q - 1$ 区间中的一个数

根据先人的经验，当 $P = 131$ 或 $13331$ 且 $Q = 2^{64}$ 时[^1]，出现冲突的概率就极小了

应用场景：

• 求出任意一段该字符串子串 $[l, r]$ 的哈希值：

$$h[l, r] = h[r] - h[l - 1] * p^{r - l + 1}$$

例题：

Acwing841-字符串哈希

const int N = 1e5 + 10, P = 131;
// P 表示 P 进制，或取 13331
 
int n, m;
char str[N];
ULL h[N], p[N];
// h[i] 表示是字符串从 1 ~ i 的哈希值 
// p[i] 表示 P 的 i 次方 

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 的次幂，提前对 p 的整数次幂进行初始化
	for (int i = 1; i <= n; i ++)
		h[i] = h[i - 1] * P + str[i];
	// 字符串哈希数组的初始化。二者合并可以优化常数
	
	int l1, r1, l2 ,r2;
	while (m --) {
		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
		if (get(l1, r1) == get(l2, r2))
			cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}

字符串哈希与KMP

我们发现，KMP 与 字符串哈希 均可进行字符串匹配。在 寻找字符串循环节 的问题中只能使用 KMP，而其他对字符串进行匹配的方法，字符串哈希不失为一种高效的方法

[^1]:对 $2^64$ 取模可直接使用 unsigned long long ，数据范围 $2^64 - 1$ ，可自然溢出