哈希表
1. 模擬散列表
把一大堆整數(shù)，范圍很大零散的，映射為在某一范圍的
例題：840. 模擬散列表
維護(hù)一個集合，支持如下幾種操作：
- “I x”，插入一個數(shù)x；
- “Q x”，詢問數(shù)x是否在集合中出現(xiàn)過；
現(xiàn)在要進(jìn)行N次操作，對于每個詢問操作輸出對應(yīng)的結(jié)果。
輸入格式
第一行包含整數(shù)N，表示操作數(shù)量。
接下來N行，每行包含一個操作指令，操作指令為”I x”，”Q x”中的一種。
輸出格式
對于每個詢問指令“Q x”，輸出一個詢問結(jié)果，如果x在集合中出現(xiàn)過，則輸出“Yes”，否則輸出“No”。
每個結(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 拉鏈法散列表
思路：和圖的臨界表存儲類似，詳見之前寫的文章：樹和圖的深度優(yōu)先搜索（應(yīng)用：樹的重心）
用一維數(shù)組存儲哈希值，對于大范圍的數(shù)，每次模上一個數(shù)p,然后映射到數(shù)組下標(biāo)，一般p取大于n的第一個質(zhì)數(shù),這樣沖突最小
x ==> h[x % p] ,h存放的是每個拉鏈的指針
平均下，每條鏈表很短，一般是O(1)算法
模板
int h[N], e[N], ne[N], idx;
// 向哈希表中插入一個數(shù)
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查詢某個數(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ù)組大小為第一個大于2n 的素?cái)?shù)*），插入時有空位就插，沒空位就找下一個空位，一直到找到為止，查詢也是如果當(dāng)前位置空了就沒有該元素，否則就判斷該元素是不是，不是就接著往前循環(huán)找，知道找到第一個空位結(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;
}
//如果有這個數(shù)就返回這個數(shù)的下標(biāo)，沒有就返回下一個空位
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é)：剛看了下，兩算法的時間復(fù)雜度一樣的，都是O(n)的，不過我更喜歡第一個拉鏈法。然后剛測了下unordered_set和unordered_map,發(fā)現(xiàn)還是上面兩個快
2. 字符串哈希
例題：841. 字符串哈希
給定一個長度為n的字符串，再給定m個詢問，每個詢問包含四個整數(shù) l1,r1,l2,r2，請你判斷[l1,r1]和[l2,r2]這兩個區(qū)間所包含的字符串子串是否完全相同。
字符串中只包含大小寫英文字母和數(shù)字。
輸入格式
第一行包含整數(shù)n和m，表示字符串長度和詢問次數(shù)。
第二行包含一個長度為n的字符串，字符串中只包含大小寫英文字母和數(shù)字。
接下來m行，每行包含四個整數(shù)l1,r1,l2,r2，表示一次詢問所涉及的兩個區(qū)間。
注意，字符串的位置從1開始編號。
輸出格式
對于每個詢問輸出一個結(jié)果，如果兩個字符串子串完全相同則輸出“Yes”，否則輸出“No”。每個結(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，取這兩個值的沖突概率低
小技巧：取模的數(shù)用2^64，這樣直接用unsigned long long存儲，溢出的結(jié)果就是取模的結(jié)果
具體點(diǎn)，就是把一個字符串如”ABC”映射成一個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í)沒這個快
