哈希表

目的：将大范围的多个数映射到一个0-N的集合中

常见哈希表：

1.普通哈希表

处理冲突方式：

​ 1.开放寻址法

image-20210911164017945 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N=2e5+3,num=0x3f3f3f3f;
int h[N];
int find(int x)
{
    int k=(x%N+N)%N;
    while(h[k]!=num&&h[k]!=x)
    {
		k++;
        if(k==N)k=0;
    }
}
//添加
int k=find(x);
h[k]=x;
//查找
int k=find(x);
if(h[k]!=num)//存在
    else //不存在

​ 2.拉链法：一个数组存储所有哈希值

image-20210911155856034

常用操作：1.添加2.查找

3.删除（额外数组进行标记，不常用）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N=1e5+3;//减少冲突经常取模100003(大于最大集合范围的最小的质数)
int h[N],e[N],ne[N],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 true;
    return false;
}

2.字符串哈希

字符串前缀哈希法：

预处理所有前缀的哈希

1

​ 1.如何定义前缀的哈希值：将其转化为p进制数

​ 注：*1.不能将任何数映射为0

​ *2.不存在冲突时，p=131或13331、Q取2^64时，不存在冲突

image-2

好处：可以依照公式求出前缀的哈希值求出一段的哈希值

image-20210911171102237公式： \[ h[R]-h[L-1]*p^(R-L+1) \]

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
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e5+10,P=131;
int n,m;
char str[N];
ull h[N],p[N];
ull get(int l,int r)
{
	return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    scanf("%d%d%s",&n,&m,str+1);
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
		p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+str[i];
    }
    while(m--)
    {
		int l1,l2,r1,r2;
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}