7、哈希表

哈希表最主要的作用就是把一个比较庞大的空间或者值域 映射到比较小的值域 (0-n)

就是将-10^9 ~10^9 映射到 0 ~10^5

一、存储结构

映射的方法可以是 h(x) = x mod 10^5

但是这样映射会出现一个问题 可能会有重复的数字出现

所以就引出了两个方法 开放寻址法 和 拉链法

1、开放寻址法

也开一个一维数组 但是一维数组的长度要是题目所给数据的2-3倍

h(x) = k

从第k个数字开始去找 如果已经存在了 就去找下一个

2、拉链法

开一个一维数组去存储值 比如映射到0~10^5

则开一个长度为10^5的数组

如图所示 当11和23都映射到3这个位置的时候

可以在3的下面开一个拉链 去记录所有映射到这个位置上的数字

题目：模拟散列表

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

I x，插入一个数 x；
Q x，询问数 x 是否在集合中出现过；
现在要进行 n 次操作，对于每个询问操作输出对应的结果。

输入格式：

第一行包含整数 n，表示操作数量。
接下来 n 行，每行包含一个操作指令，操作指令为I x，Q x中的一种。

输出格式：

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

数据范围：

1≤n≤10^5

-10^9<=x <= 10^9

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

代码一(拉链法)：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10010;

int h[N];
int e[N], ne[N], idx;

void insert(int x)
{
	//首先先把x映射到数组中去
	int k = (x % N + N) % N;

	e[idx] = k;
	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++)
	{
		if (e[i] = k) return true;
	}
	return false;
}

int main()
{
	int n; cin >> n;
	memset(h,-1,sizeof h);
	while (n--)
	{
		char op[2];
		scanf("%s",op);
		if (op[0] == 'I')
		{
			int x; cin >> x;
			insert(x);
		}
		else {
			int x; cin >> x;
			if (find(x)) cout << "Yes";
			else  cout << "No";
		}
	}

	return 0;
}

二、字符串哈希的方式

O(1)

快速判断两个字符串是否相等

就可以用该方法

字符串前缀哈希法

给定一个字符串

首先预处理所有前缀的哈希值

(如何来定义每一个前缀的哈希值)

p进制

假设A-Z个字母 求出这个数组的十进制数字

(相加的结果可能过于大 所以mod上一个数字) 、

就可以把整个数字映射到0 - Q-1上

注意

1、不能够映射成0

如果可以的话 A -> 0 AA-> 0 重复了

2、不存在冲突的情况

p = 131 或者13331

Q = 2^64

这样取值 在一般情况下 可以假定不会出现冲突

怎么求出 L-R这一段的哈希值

把1-R的所有的数字 看成是p进制的数字 左边是高位 右边是低位

即 在h[R]中 R就是第0位 1就是R-1位

h[L-1] 中 L-1就是第0位 1是L-2位

已知从1-R的哈希值h[R] = p^(r-1) ….p^0

和1-L-1 的哈希值 h[L-1] = p^(l-2) …….p ^0

因此让h[L-1] * p^(R-L+1) =》作用是让h[L]往右移动若干位 与h[R]对齐

*=》h[R] - h[L-1] p^(R-L+1)

思路整理

• 把字符串看成是一个 P 进制数，每个字符的 ASCII 码对应数的一位
• ASCII 范围 0 - 127，最少 128 进制，经验上取 131 或 13331 冲突率低
• 字符串很长，对应的数太大，通过模 2^64 把它映射到 [0, 2^64 - 1]
• 用 unsigned long long 存储，溢出相当于对 2^64 取模，省略了手动运算
• 该方法的好处是，可以利用前缀哈希直接求出子串哈希（减去高位）

hash(DEF) = hash(ABCDEF) - hash(ABC) x P^3
    1       2       3       4       5       6
    A       B       C       D       E       F  
  1xP^5 + 2xP^4 + 3xP^3 + 4xP^2 + 5xP^1 + 6xP^0

                            D       E       F
                          4xP^2 + 5xP^1 + 6xP^0

    A       B       C  
  1xP^2 + 2xP^1 + 3xP^0

题目描述 字符串哈希

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

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

输入格式

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

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

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

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

输出格式

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

每个结果占一行。

数据范围

1≤𝑛,𝑚≤10^5

输入样例：

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

输出样例：

Yes
No
Yes

代码

#include <iostream>

using namespace std;
typedef unsigned long long ULL;

const int N = 100010,P = 131;
char str[N];
ULL h[N], p[N];//p数组用来存储p的多少次方的

ULL get(int l, int r)
{
	return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
	int n,m; cin >> n >> m;
	cin >> str + 1;
	p[0] = 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)) cout << "yes";
		else cout << "NO";
	}

	return 0;
}