【c++提高1】数据结构之哈希表

大纲

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
2
3
4
5

步骤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++;
}
1
2
3
4
5
6

步骤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;
}
1
2
3
4
5
6

(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
2
3
4
5

步骤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;
}
1
2
3
4
5
6
7
8

没有步骤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');
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

开放寻址法：

/*
开放寻址法
*/
#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');
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

拉链法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<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');
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

3.哈希表变形：字符串哈希

题目大意：

给定一个字符串s，长度为n，有m个查询。
每一个查询包含四个整数：
l1, r1, l2, r2，询问子串[l1, r1]和子串[l2,r2]是否相同。

接下来讲的哈希方法是字符串前缀哈希法。
每次先预处理哈希值，就比如字符串是：

AABABBBABSAJJ
1

伪Hash表应该表示的是前缀的字符串：

h[1] = "A";
h[2] = "AA";
h[3] = "AAB";
h[4] = "AABA";
.....
1
2
3
4
5

依次类推。
然而真正的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];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

步骤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");
}
1
2
3
4
5
6

取模法就不不讲了，计算的时候在原基础上取模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");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

基本上就这样吧