哈希表 | OI笔记

哈希表

基本思想：

将大范围的复杂数据按照一个固定操作 h(x) 映射到小范围的简单数据，例如 h(x) = x % 1e5 + 3

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

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

拉链法 和 开放寻址法

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

拉链法：

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

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

插入操作：

void insert(int x)
// 链表头插法 
{
	int k = (x % N + N) % N;
	// 将所有数映射到 0 ~ 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;
		// 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 * p^1^ + 2 * p^0^
h[3] = 1 * p^2^ + 2 * p^1^ + 3 * p^0^
…………

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

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

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

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

应用场景：

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

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

例题：

Acwing841-字符串哈希

typedef unsigned long long ULL;

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 的整数次幂进行初始化
		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))
			cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	
	return 0;
}

字符串哈希与KMP

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

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