一、一般哈希表
1.算法模板
(1) 拉链法 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) 开放寻址法 int h[N]; // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置 int find(int x) { int t = (x % N + N) % N; while (h[t] != null && h[t] != x) { t ++ ; if (t == N) t = 0; } return t; }
2.拉链法：
3.开放寻址法：(蹲坑法)
4.例题：
维护一个集合，支持如下几种操作：
- I x，插入一个数 x；
- Q x，询问数 x 是否在集合中出现过；
现在要进行 N 次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N，表示操作数量。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。
输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x在集合中出现过，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤N≤10^5
-10^9≤x≤10^9
输入样例：
5 I 1 I 2 I 3 Q 2 Q 5
输出样例：
Yes No
拉链法：
#include<bits/stdc++.h> using namespace std; const int N=100003;// 取大于1e5的第一个质数，取质数冲突的概率最小 可以百度 //* 开一个槽 h int h[N],e[N],ne[N],idx;//邻接表 void insert(int x) { // c++中如果是负数 那他取模也是负的所以加N再%N就一定是一个正数 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; //用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数 for(int i=h[k];i!=-1;i=ne[i]) { if(e[i]==x)return true; } return false; } int main() { memset(h,-1,sizeof h); //将槽先清空 空指针一般用 -1 来表示 int n; cin>>n; while(n--) { int x; char op; cin>>op>>x; if(op=='I') insert(x); else { if(find(x))cout<<"Yes"<<endl; else cout<<"No"<<endl; } } return 0; }
*开放寻址法：
#include<bits/stdc++.h> using namespace std; //开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了 const int N=200003;//大于数据范围的第一个质数 const int null=0x3f3f3f3f;//规定空指针为 null 0x3f3f3f3f int h[N]; int find(int x) { int k=(x%N+N)%N; while(h[k]!=null&&h[k]!=x) { k++; if(k==N) { k=0; } } return k;//如果这个位置是空的, 则返回的是他应该存储的位置 } int main() { memset(h,null,sizeof h);//规定空指针为 0x3f3f3f3f int n; cin>>n; while(n--) { char op; int x; cin>>op>>x; int k=find(x); if(op=='I')h[k]=x; else { if(h[k]!=null)cout<<"Yes"<<endl; else cout<<"No"<<endl; } } }
***二、字符串哈希
1.*算法模板(注意计算公式)
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低 小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果 typedef unsigned long long ULL; ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64 // 初始化 void init() { //字符串从1开始编号，h[1]为前一个字符的哈希值 p[0] = 1; h[0] = 0; for(int i=0;i<n;i++) { p[i+1] = p[i]*P; h[i+1] = h[i]*P +s[i]; //前缀和求整个字符串的哈希值 } } // 计算子串 str[l ~ r] 的哈希值 ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }
2.思路：
字符串哈希) O(n)+O(m)
全称字符串前缀哈希法，把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字。
对形如 X1X2X3⋯Xn−1Xn 的字符串,采用字符的ascii 码乘上 P 的次方来计算哈希值。
注意点：
1. 任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0
2. 冲突问题：通过巧妙设置P (131 或 13331) , Q (2^64)的值，一般可以理解为不产生冲突。
常见问题是比较不同区间的子串是否相同，就转化为对应的哈希值是否相同。
求一个字符串的哈希值就相当于求前缀和，求一个字符串的子串哈希值就相当于求部分和
3.例题：
给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2请你判断 [l1,r1]和 [l2,r2]这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n和 m，表示字符串长度和询问次数。
第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。
接下来 m行，每行包含四个整数 l1,r1,l2,r2表示一次询问所涉及的两个区间。
注意，字符串的位置从 1 开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤10^5
输入样例：
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; const int N=100010,P=131; typedef unsigned long long ULL; ULL h[N],p[N]; // h[i]前i个字符的hash值 // 字符串变成一个p进制数字，体现了字符+顺序，需要确保不同的字符串对应不同的数字 // P = 131 或 13331 Q=2^64，在99%的情况下不会出现冲突 // 使用场景： 两个字符串的子串是否相同 string s; int n,m; void init() { //字符串从1开始编号，h[1]为前一个字符的哈希值 p[0] = 1; h[0] = 0; for(int i=0;i<n;i++) { p[i+1] = p[i]*P; h[i+1] = h[i]*P +s[i]; //前缀和求整个字符串的哈希值 } } ULL get(int l,int r) { return h[r]-h[l-1]*p[r-l+1]; } int main() { cin>>n>>m; cin>>s; init(); while(m--) { int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2; if(get(l1,r1)==get(l2,r2)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } }
