大纲
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; //10003是1e5上最小的质数
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
#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; //10003是1e5上最小的质数
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
#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; //10003是1e5上最小的质数
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版：
/*
拉链法vector版
*/
#include
#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; //10003是1e5上最小的质数
vector
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
#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");
}
}
基本上就这样吧
文章来源
发表评论