2.5 哈希表
概念
- 对于处理复杂大量的信息,我们将这些信息映射到一个容易操作的区间内,如将
-1e9~1e9
范围的数映射到0~1e5
的范围内,以便于我们对这些数据进行插入,查询,删除等操作。
2.5.1 模拟散列表存储
操作思想(拉链法)
- 取质数
N = 1e6+3
作为映射的标准(一般来说,质数造成的冲突更小) - 对于一组数据,将映射作为一维数组的下标来存储
- 如果对于两个不同的数据,他们的映射相同,则在该映射下新建一个结点来存储,解决冲突
模板
const int N=1e6+3; //映射的标准
int h[N],e[N],ne[N]; //h[N]存储映射,初始化为-1 e[N]存储原值 ne[N]存储下一个结点的指针
int idx; //充当指针作用
void init(){ //初始化操作
for(int i=0;i<N;i++) h[i]=-1;
}
void insert(int x){ //插入操作
int k=(x%N+N)%N; //对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 1;
}
return 0;
}
例题 840. 模拟散列表
描述
维护一个集合,支持如下几种操作:
I x
,插入一个数 x;Q x
,询问数 x 是否在集合中出现过;
现在要进行 N 次操作,对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N,表示操作数量。
接下来 N 行,每行包含一个操作指令,操作指令为 I x,Q x 中的一种。
输出格式
对于每个询问指令 Q x,输出一个询问结果,如果 x 在集合中出现过,则输出 Yes,否则输出 No。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
输出样例:
5
I 1
I 2
I 3
Q 2
Q 5
输出样例:
Yes
No
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+3;
int h[N],e[N],ne[N];
int 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){
int k=(x%N+N)%N;
for(int i=h[k];i!=-1;i=ne[i]){
if(e[i]==x) return 1;
}
return 0;
}
int main(){
for(int i=0;i<N;i++) h[i]=-1;
int n;
cin>>n;
while(n--){
char op[10];
int x;
scanf("%s %d",op,&x);
if(*op=='I'){
insert(x);
}
else{
if(find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
2.5.2 字符串前缀哈希
操作思想
- 把字符串变成一个
P
进制数字,实现不同的字符串映射到不同的数字 - 对形如
X1 X2 X3⋯Xn−1 Xn
的字符串,采用字符的ASCII
码乘上P
的次方来计算哈希值 - 映射处理为该哈希值对
Q
进行取模:(X1 * P^n−1 + X2 * P^n−2+⋯+ Xn−1 * P^1 + Xn * P^0)%Q
注意点
- 任意字符不可以映射成
0
,否则会出现不同的字符串都映射成0的情况,比如A,AA,AAA
皆为0
- 冲突问题:
P = (131 或 13331)
,Q = 2 ^ 64
,一般情况下不产生冲突。 - 对于
Q
取模,我们用unsigned long long
自然溢出来解决
模板
typedef unsigned long long ULL;
const ULL N=1e6+3,P=131;
ULL h[N],p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
string s;
cin>>s; //读入字符串s
// 初始化前i个字符的哈希值
p[0]=1;
for(int i=1;i<=s.size();i++){
h[i]=h[i-1]*P+s[i]; //前缀和求整个字符串的哈希值
p[i]=p[i-1]*P; //存储每一位的权值
}
// 计算子串str[l~r]的哈希值
ULL find(int l, int r){
return h[r]-h[l-1]*p[r-l+1]; //将h[l-1]的高位与h[r]的最高位置的权值相对齐
}
例题 841. 字符串哈希
描述
给定一个长度为 n 的字符串,再给定 m 个询问,每个询问包含四个整数 l1,r1,l2,r2,请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n 和 m,表示字符串长度和询问次数。
第二行包含一个长度为 n 的字符串,字符串中只包含大小写英文字母和数字。
接下来 m 行,每行包含四个整数 l1,r1,l2,r2,表示一次询问所涉及的两个区间。
注意,字符串的位置从 1 开始编号。
输出格式
对于每个询问输出一个结果,如果两个字符串子串完全相同则输出 Yes,否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤105
输出样例:
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例:
Yes
No
Yes
代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=1e6+3,P=131;
ULL h[N],p[N];
ULL find(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
int n,m;
cin>>n>>m;
string s;
cin>>s;
p[0]=1;
for(int i=0;i<s.size();i++){
p[i+1]=p[i]*P;
h[i+1]=h[i]*P+s[i];
}
while(m--){
int l1,l2,r1,r2;
cin>>l1>>r1>>l2>>r2;
if(find(l1,r1)==find(l2,r2)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}