大纲
1.哈希表存储方式
2.哈希表应用：散射表
3.哈希表变形：字符串哈希
4.例题
1.哈希表存储方式
(1)主要思想
哈希表的主要思想是将一个大空间，映射到一个系统可以承受的小空间，一般是映射为0~N。
一般常见的是将0 ~ 1e9映射成0 ~ 1e5，1e9的空间肯定是会爆的吧。
说实话很像离散化
(2)哈希冲突
哈希表的核心是一个哈希函数f(x)，对于一个数字x(0 ~ 1e9)，映射为y(0~1e5)。
实现：
方法1：取模
直接将x对1e5取模即可。
常见问题：
哈希冲突
哈希冲突：将两个不同的数映射成了同一个数。
比如：10和1e6，1e6 mod 1e5 = 10, 10 mod 1e5 = 10, 哈希函数值相同
所以需要找到一种更好的函数解决哈希冲突这个问题。
(3)哈希正确实现方法1
实现方法：拉链法
用一个1e5的一维数组，来存储哈希值。
哈希冲突解决方式：当把一个x映射到某一个数的时候，将mod的结果(y)的下面拉一条链x。
这样如果有两个哈希值冲突的话，就会把这两个值都拉一条链。这个链可以使用单链表实现，每次在查找x的时候就在hash[y]下面的链找一遍看看有没有x。
取模的数最好的数是一个质数并且离2的整数幂远，这个在数学上是可以推到出来的，在这里不多说了。
题目如果有负数的话有两种应对办法：
1.开两个哈希表（负数，正数）。
2.小技巧：(x%mod+mod)%mod
拉链法实现：
步骤0：定义链表，并初始化。
const int maxn=1e5+3;
int h[maxn],e[maxn],ne[maxn],idx;
void init(){
memset(h,-1,sizeof(h));
}
步骤1：对x加入hash
得到x对应的f(x)，并且通过链表拉条链x。
void add(int x){
int k=(x%maxn+maxn)%maxn;
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
步骤2：查询x是否在hash里
得到对应的f(x)，并且遍历hash[f(x)]的链，查询是否存在x。
bool find(int x){
int k=(x%maxn+maxn)%maxn;
for(int i=h[k];~i;i=ne[i])
if(e[i]==x)return 1;
return 0;
}
(4)哈希正确实现方法2
实现方法：开放寻址法
哈希冲突解决方法：
首先数组需要开到2~3倍。
设f(x)=y，那么首先看hash[y]是否已经有hash值了，如果是，就往后移动一格，重复操作1，直到hash[z]没有hash值了，就存入x
首先初始化为一个不可能的值，接下俩就可以一个while循环判断当前hash[i]位置是否有hash值，一直往后移模拟即可。
开放寻址法代码实现：
步骤0：初始化为0x3f3f3f3f
const int maxn=2e5+3;
int h[maxn];
void init(){
memset(h,0x3f,sizeof(h));
}
步骤1：find(x)函数，如果hash[f(x)]没有值，就直接返回f(x)即可，否则返回后面第一个没有hash值的位置。
注意：在判断的时候还需要判断当前位置不为x，x有可能以前存在过，就别让它在跑下去了。
int find(int x){
int k=(x%maxn+maxn)%maxn;
while(h[k]!=0x3f3f3f3f&&h[k]!=x){
k++;
if(k==maxn) k=0;
}
return k;
}
没有步骤2了
2.哈希表应用散射表
hash-散射表
题意：
一个集合。
操作1：将x加入集合
操作2：问x是否存在于集合中。
两种方法直接用即可。
拉链法：
#include<bits/stdc++.h>
#define FOR(x,y,z) for(int x=y,x_=z;x<=x_;x++)
#define DOR(x,y,z) for(int x=y,x_=z;x>=x_;x--)
#define ll long long
using namespace std;
void read(int& x){
char c;x=0;
int f=1;
while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
do x=(x<<3)+(x<<1)+(c^48);
while(c=getchar(),c>='0'&&c<='9');
x*=f;
}
void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+48);
}
const int maxn=1e5+3;
int h[maxn],e[maxn],ne[maxn],idx;
void add(int x){
int k=(x%maxn+maxn)%maxn;
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
bool find(int x){
int k=(x%maxn+maxn)%maxn;
for(int i=h[k];~i;i=ne[i])
if(e[i]==x)return 1;
return 0;
}
int main(){
int n; read(n);
memset(h,-1,sizeof(h));
FOR(i,1,n){
char Q[2]; int x;
scanf("%s%d", Q, &x);
if(*Q=='I')add(x);
else{
if(find(x))printf("Yes");
else printf("No");
putchar('\n');
}
}
}
开放寻址法：
#include<bits/stdc++.h>
#define FOR(x,y,z) for(int x=y,x_=z;x<=x_;x++)
#define DOR(x,y,z) for(int x=y,x_=z;x>=x_;x--)
#define ll long long
using namespace std;
void read(int& x){
char c;x=0;
int f=1;
while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
do x=(x<<3)+(x<<1)+(c^48);
while(c=getchar(),c>='0'&&c<='9');
x*=f;
}
void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+48);
}
const int maxn=2e5+3;
int h[maxn];
void init(){
memset(h,0x3f,sizeof(h));
}
int find(int x){
int k=(x%maxn+maxn)%maxn;
while(h[k]!=0x3f3f3f3f&&h[k]!=x){
k++;
if(k==maxn)k=0;
}
return k;
}
int main(){
int n; read(n);
init();
FOR(i,1,n){
char Q[2]; int x;
scanf("%s%d", Q, &x);
int k=find(x);
if(*Q=='I')h[k]=x;
else{
if(h[k]!=0x3f3f3f3f)printf("Yes");
else printf("No");
putchar('\n');
}
}
}
拉链法vector版：
#include<bits/stdc++.h>
#define FOR(x,y,z) for(int x=y,x_=z;x<=x_;x++)
#define DOR(x,y,z) for(int x=y,x_=z;x>=x_;x--)
#define ll long long
using namespace std;
void read(int& x){
char c;x=0;
int f=1;
while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
do x=(x<<3)+(x<<1)+(c^48);
while(c=getchar(),c>='0'&&c<='9');
x*=f;
}
void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+48);
}
const int maxn=1e5+3;
vector<int> edge[maxn];
void add(int x){
int k=(x%maxn+maxn)%maxn;
edge[k].push_back(x);
}
bool find(int x){
int k=(x%maxn+maxn)%maxn;
for(int e:edge[k])
if(e==x)return 1;
return 0;
}
int main(){
int n; read(n);
FOR(i,1,n){
char Q[2]; int x;
scanf("%s%d", Q, &x);
if(*Q=='I')add(x);
else{
if(find(x))printf("Yes");
else printf("No");
putchar('\n');
}
}
}
3.哈希表变形：字符串哈希
题目大意：
给定一个字符串s，长度为n，有m个查询。
每一个查询包含四个整数：
l1, r1, l2, r2，询问子串[l1, r1]和子串[l2,r2]是否相同。
接下来讲的哈希方法是字符串前缀哈希法。
每次先预处理哈希值，就比如字符串是：
AABABBBABSAJJ
伪Hash表应该表示的是前缀的字符串：
h[1] = "A";
h[2] = "AA";
h[3] = "AAB";
h[4] = "AABA";
.....
依次类推。
然而真正的h[i]其实表示的是前缀字符串所对应的哈希值，预处理的就是前缀hash值。
一、Hash值定义
二、如何使用Hash值算区间[l, r]
可以把字符串看成是一个P进制的数，字符串的字母就表示P进制的每一位数字，指它的ascii码。
但是字符串哈希也会有哈希冲突，当P的取值是131或是13331的时候冲突最小。
2.
现在已知的hash值（或者说可以用到的hash值）是[1, l - 1]的hash值和[1, r]的hash值，要通过他们得出[l, r]的hash值。
左边是高位，因为看成的是一个P进制数。
因为这个P的问题，所以要把hash[l - 1]往r移动，怎样实现呢？
可以发现，区别就在于乘P，将l - 1移动到r共需要r - l + 1次，所以乘一次P就相当于移动一位，乘以r - l + 1次P就可以了。
注意：因为值很大，所以有两种方法解决：
① long long+取模。
将每一个hash[i]都对一个大质数取模。
② 方便，unsigned long long自然溢出
用unsigned long long存储hash[i]，超出范围时自然溢出。
str_hash实现
① 自然溢出法
步骤1：预处理前缀hash值，因为计算时需要乘P^ (r-l+1)，所以可以预处理每一个p[i] = P^ i，调用的时候直接h[r] - h[l - 1] * p[r - l + 1];
typedef unsigned long long ull;
const int maxn=1e5+10,P=131;
ull p[maxn],h[maxn];
void hash_init(){
p[0]=1;
for(int i=1;i<=n;i++){
p[i]=p[i-1]*P;
h[i]=h[i-1]*P+str[i];
}
}
ull query(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
步骤2：查询，每次判断[l, r]hash值。
while(m--){
int l1,r1,l2,r2;
read(l1),read(r1),read(l2),read(r2);
if(query(l1,r1)==query(l2,r2))printf("Yes\n");
else printf("No\n");
}
取模法就不不讲了，计算的时候在原基础上取模P即可。
完整代码：
#include<bits/stdc++.h>
#define FOR(x,y,z) for(int x=y,x_=z;x<=x_;x++)
#define DOR(x,y,z) for(int x=y,x_=z;x>=x_;x--)
#define ll long long
using namespace std;
void read(int& x){
char c;x=0;
int f=1;
while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
do x=(x<<3)+(x<<1)+(c^48);
while(c=getchar(),c>='0'&&c<='9');
x*=f;
}
void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+48);
}
typedef unsigned long long ull;
const int maxn=1e5+10,P=131;
int n,m; char str[maxn];
ull p[maxn],h[maxn];
void hash_init(){
p[0]=1;
FOR(i,1,n)p[i]=p[i-1]*P,h[i]=h[i-1]*P+str[i];
}
ull query(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main(){
read(n),read(m);
scanf("%s",str+1);
hash_init();
while(m--){
int l1,l2,r1,r2;
read(l1),read(r1),read(l2),read(r2);
if(query(l1,r1)==query(l2,r2))printf("Yes\n");
else printf("No\n");
}
}
基本上就这样吧
|