7、哈希表
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^31 2 3 4 5 6A B C D E F 1xP^5 + 2xP^4 + 3xP^3 + 4xP^2 + 5xP^1 + 6xP^0D E F4xP^2 + 5xP^1 + 6xP^0A 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次方为1for (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;
}