哈希表
1. 模擬散列表
把一大堆整數(shù)串纺，范圍很大零散的，映射為在某一范圍的
例題：840. 模擬散列表
維護(hù)一個(gè)集合搓萧，支持如下幾種操作：
- “I x”，插入一個(gè)數(shù)x；
- “Q x”压彭，詢問數(shù)x是否在集合中出現(xiàn)過闻妓；
現(xiàn)在要進(jìn)行N次操作菌羽，對(duì)于每個(gè)詢問操作輸出對(duì)應(yīng)的結(jié)果。
輸入格式
第一行包含整數(shù)N由缆，表示操作數(shù)量注祖。
接下來N行，每行包含一個(gè)操作指令均唉，操作指令為”I x”是晨，”Q x”中的一種。
輸出格式
對(duì)于每個(gè)詢問指令“Q x”舔箭，輸出一個(gè)詢問結(jié)果罩缴，如果x在集合中出現(xiàn)過蚊逢，則輸出“Yes”，否則輸出“No”箫章。
每個(gè)結(jié)果占一行烙荷。
數(shù)據(jù)范圍
1≤N≤10^5
?109≤*x*≤109
輸入樣例：
5
I 1
I 2
I 3
Q 2
Q 5
輸出樣例：
Yes
No
1.1 拉鏈法散列表
思路：和圖的臨界表存儲(chǔ)類似，詳見之前寫的文章：樹和圖的深度優(yōu)先搜索（應(yīng)用：樹的重心）
用一維數(shù)組存儲(chǔ)哈希值檬寂，對(duì)于大范圍的數(shù)终抽，每次模上一個(gè)數(shù)p,然后映射到數(shù)組下標(biāo)，一般p取大于n的第一個(gè)質(zhì)數(shù),這樣沖突最小
x ==> h[x % p] ,h存放的是每個(gè)拉鏈的指針
平均下桶至，每條鏈表很短昼伴，一般是O(1)算法
模板
int h[N], e[N], ne[N], idx;
// 向哈希表中插入一個(gè)數(shù)
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查詢某個(gè)數(shù)是否存在
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;
}
- 模擬散列表
#include <iostream>
#include <cstring>
using namespace std;
int n,x;
const int N = 100003;
int h[N],e[N],ne[N],idx;
void insert(int x);
bool find(int x);
int main(){
cin>>n;
memset(h,-1,sizeof h);
while(n--){
char op[2];
scanf("%s%d",op,&x);
if(*op == 'I')
insert(x);
else{
if(find(x))
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}
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;
}
1.2 開放尋址法
思路：只開一維數(shù)組(一般數(shù)組大小為第一個(gè)大于2n 的素?cái)?shù)*），插入時(shí)有空位就插镣屹，沒空位就找下一個(gè)空位圃郊，一直到找到為止，查詢也是如果當(dāng)前位置空了就沒有該元素女蜈，否則就判斷該元素是不是持舆，不是就接著往前循環(huán)找，知道找到第一個(gè)空位結(jié)束（注意鞭光，由于數(shù)組夠大吏廉，所以一定有空位）
#include <iostream>
#include <cstring>
using namespace std;
int n,x;
const int N = 200003;
const int null = 0x3f3f3f3f;
int h[N];
int find(int x);
int main(){
cin>>n;
memset(h,0x3f,sizeof h);
while(n--){
char op[2];
scanf("%s%d",op,&x);
int t = find(x);
if(*op == 'I'){
h[t] = x;
}
else{
if(h[t] != null)
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}
//如果有這個(gè)數(shù)就返回這個(gè)數(shù)的下標(biāo)，沒有就返回下一個(gè)空位
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;
}
總結(jié)：剛看了下惰许，兩算法的時(shí)間復(fù)雜度一樣的席覆，都是O(n)的，不過我更喜歡第一個(gè)拉鏈法汹买。然后剛測(cè)了下unordered_set和unordered_map,發(fā)現(xiàn)還是上面兩個(gè)快
2. 字符串哈希
例題：841. 字符串哈希
給定一個(gè)長(zhǎng)度為n的字符串佩伤，再給定m個(gè)詢問，每個(gè)詢問包含四個(gè)整數(shù) l1,r1,l2,r2晦毙，請(qǐng)你判斷[l1,r1]和[l2,r2]這兩個(gè)區(qū)間所包含的字符串子串是否完全相同生巡。
字符串中只包含大小寫英文字母和數(shù)字。
輸入格式
第一行包含整數(shù)n和m见妒，表示字符串長(zhǎng)度和詢問次數(shù)孤荣。
第二行包含一個(gè)長(zhǎng)度為n的字符串，字符串中只包含大小寫英文字母和數(shù)字须揣。
接下來m行盐股，每行包含四個(gè)整數(shù)l1,r1,l2,r2，表示一次詢問所涉及的兩個(gè)區(qū)間耻卡。
注意疯汁，字符串的位置從1開始編號(hào)。
輸出格式
對(duì)于每個(gè)詢問輸出一個(gè)結(jié)果卵酪，如果兩個(gè)字符串子串完全相同則輸出“Yes”幌蚊，否則輸出“No”谤碳。每個(gè)結(jié)果占一行。
數(shù)據(jù)范圍
1≤n,m≤10^5
輸入樣例：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
輸出樣例：
Yes
No
Yes
核心思想：將字符串看成P進(jìn)制數(shù)溢豆，P的經(jīng)驗(yàn)值是131或13331蜒简，取這兩個(gè)值的沖突概率低
小技巧：取模的數(shù)用2^64，這樣直接用unsigned long long存儲(chǔ)沫换，溢出的結(jié)果就是取模的結(jié)果
具體點(diǎn)臭蚁，就是把一個(gè)字符串如”ABC”映射成一個(gè)p進(jìn)制的數(shù)字
“ABC” –> p^2+A + p^1+B + p^0+C = 哈希值最铁， 一般p取131或13331
"ABCDEFGHI"
123456789 (下標(biāo))
L R
字符串"A"的 哈希值為 p^0+A
字符串"AB" 哈希值為 p^1+A + p^0+B
字符串"ABC" 哈希值為 p^2+A + p^1+B + C
字符串[1,L-1]的哈希值為 p^3+A + p^2+B + p^1+C + p^0+D
字符串[1,R] 的哈希值為 p^8+A + p^7+B + ... + P^0+I
h[r] - h[l - 1] * p[r - l + 1]
注：此處看的別人的題解才看懂的：https://www.acwing.com/solution/content/3613/
代碼：
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, 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", &n, &m);
scanf("%s", str + 1);
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
while (m -- )
{
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}
總結(jié)：今天用stl中的string中的sunstr()方法試了試讯赏，發(fā)現(xiàn)效率確實(shí)沒這個(gè)快
