作者：指針不指南嗎
專欄：算法篇

🐾或許會(huì)很慢，但是不可以停下來(lái)🐾

1.定義

• 哈希表（Hash table），是根據(jù)鍵（Key）直接訪問(wèn)在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，這樣就加快了查找速度。這個(gè)映射函數(shù)稱做散列函數(shù)（哈希函數(shù)），存放記錄的數(shù)組稱做散列表。

• 就是把一堆龐大數(shù)據(jù)映射到一個(gè)小的數(shù)據(jù)結(jié)構(gòu)中，比如把0~$10^9$ 映射到0~$10^5$ 的數(shù)組中。

  h(x)一般用x mod n，n表示數(shù)組大小，一般取一個(gè)質(zhì)數(shù)，這樣沖突出現(xiàn)的概率比較小。

• 沖突：當(dāng)兩個(gè)不一樣的數(shù)，通過(guò)哈希函數(shù)，映射成一個(gè)數(shù)的時(shí)候，我們無(wú)法確定這兩個(gè)數(shù)了，被稱為沖突。

2.優(yōu)點(diǎn)

查找速度快

• 哈希表是種數(shù)據(jù)結(jié)構(gòu)，它可以提供快速的插入操作和查找操作。

• 不論哈希表中有多少數(shù)據(jù)，插入和刪除，只需要接近常量的時(shí)間即 O( 1 ) 的時(shí)間復(fù)雜度。

  哈希表運(yùn)算得非?？?#xff0c;在計(jì)算機(jī)程序中，如果需要在一秒種內(nèi)查找上千條記錄通常使用哈希表（例如拼寫(xiě)檢查器)哈希表的速度明顯比樹(shù)快，樹(shù)的操作通常需要O(N)的時(shí)間級(jí)。哈希表不僅速度快，編程實(shí)現(xiàn)也相對(duì)容易。

3.數(shù)字哈希

數(shù)字哈希是數(shù)字到數(shù)字的映射關(guān)系。

3.1拉鏈法

• 操作

  • 開(kāi)一個(gè)一維數(shù)組來(lái)存儲(chǔ)哈希值；

  • 添加值（處理沖突）

    • 把每一個(gè)數(shù)組變量看成是一個(gè)槽，在槽上拉一個(gè)鏈，映射 h(x)出來(lái)是對(duì)應(yīng)在槽，即添加在其鏈上。

    • 每條鏈上的數(shù)的個(gè)數(shù)，期望值是2個(gè)

      • 整個(gè)數(shù)組鏈表大致地樣子

    

    • 將一個(gè)數(shù)插在鏈表上面

    

  • 查找值

    映射h(x)一下 x ，遍歷一下，它對(duì)應(yīng) 槽的鏈上，有沒(méi)有它

  • 刪除值

    我們不會(huì)直接把它刪掉，而是定義一個(gè)標(biāo)記 bool，在對(duì)應(yīng)想要?jiǎng)h除的數(shù)值上，打一個(gè)標(biāo)記。

• 代碼實(shí)現(xiàn)

  • 向哈希表中插入一個(gè)數(shù)

  void insert(int x) 
  {int k=(x%N+N)%N;  //哈希（映射）函數(shù)，先取模再加N，再取模，是為了保證最后的值是正數(shù)e[idex]=x;   //插在對(duì)應(yīng)槽的鏈表里面ne[idex]=h[k];h[k]=idex++;
  }
  

  • 在哈希表中查詢某個(gè)數(shù)是否存在

  bool find(int x)  
  {int k=(x%N+N)%N;  //先找出對(duì)應(yīng)的槽for(int i=h[k];i!=-1;i=ne[i]){  //遍歷槽的鏈表，查找是否有相同的值if(e[i]==x) return true;}return false;
  }
  

3.2開(kāi)放尋址法

• 操作

  • 只開(kāi)一個(gè)一維數(shù)組，數(shù)組的大小按經(jīng)驗(yàn)來(lái)說(shuō)一般是 數(shù)據(jù)范圍的2~3倍；
  • 先看一下，對(duì)應(yīng)的槽里有沒(méi)有數(shù)，有數(shù)的話，找下一槽，直到找到?jīng)]有數(shù)的槽；

• 代碼實(shí)現(xiàn)

  int h[N];
  int null=0x3f3f3f3f;
  // 如果x在哈希表中，返回x的下標(biāo)；如果x不在哈希表中，返回x應(yīng)該插入的位置
  int find(int x)
  {int k = (x % N + N) % N;  //函數(shù)映射到槽上while (h[k] != null && h[k] != x)  //這個(gè)槽里面有數(shù)，并且·這個(gè)數(shù)不是我，循環(huán)繼續(xù){k ++ ;  //找下一個(gè)槽if (k == N) k = 0;  //如果找到最后了，返回0，繼續(xù)尋找}return t;
  }
  

  • 添加元素：

    find(x)=x x不在哈希表里面，find的返回值就是該插入的位置

  • 查找元素：

    int k = find(x) 如果x不在哈希表中，返回x應(yīng)該插入的位置,則該位置為空

    h[k]==null 說(shuō)明哈希表里面沒(méi)有這個(gè)值

  • 刪除元素：

    和拉鏈法一樣，定義一個(gè)bool變量，用作標(biāo)記

3.3 例題

維護(hù)一個(gè)集合，支持如下幾種操作：

1. I x，插入一個(gè)數(shù) x；
2. Q x，詢問(wèn)數(shù) x 是否在集合中出現(xiàn)過(guò)；

現(xiàn)在要進(jìn)行 N 次操作，對(duì)于每個(gè)詢問(wèn)操作輸出對(duì)應(yīng)的結(jié)果。

輸入格式

第一行包含整數(shù) N，表示操作數(shù)量。

接下來(lái) N 行，每行包含一個(gè)操作指令，操作指令為 I x，Q x 中的一種。

輸出格式

對(duì)于每個(gè)詢問(wèn)指令 Q x，輸出一個(gè)詢問(wèn)結(jié)果，如果 x 在集合中出現(xiàn)過(guò)，則輸出 Yes，否則輸出 No。

每個(gè)結(jié)果占一行。

數(shù)據(jù)范圍

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;  // N取100010的最大質(zhì)數(shù)，100003
  int h[N],ne[N],e[N],idex;  //h表示數(shù)組中的槽，剩下的表示鏈表有關(guān)
  int n;void insert(int x)  //添加值的函數(shù)
  {int k=(x%N+N)%N;  //哈希（映射）函數(shù)，先取模再加N，再取模，是為了保證最后的值是正數(shù)e[idex]=x;   //插在對(duì)應(yīng)槽的鏈表里面ne[idex]=h[k];h[k]=idex++;
  }bool find(int x)   //查找值的函數(shù)
  {int k=(x%N+N)%N;  //先找出對(duì)應(yīng)的槽for(int i=h[k];i!=-1;i=ne[i]){  //遍歷槽的鏈表，查找是否有相同的值if(e[i]==x) return true;}return false;
  }int main()
  {scanf("%d",&n );  //讀入操作次數(shù)memset(h,-1,sizeof h);  //清空數(shù)組，空指針一般用 -1 表示char op[2];   //讀入一個(gè)字符的時(shí)候，直接用字符數(shù)組讀入，降低出錯(cuò)率int x;  while(n--){scanf("%s%d",op,&x);  //讀入要操作的類型以及數(shù)據(jù)if(op[0]=='I') insert(x);else{if(find(x)) puts("Yes");else puts("No");}}return 0;
  }
  

• 方法二：開(kāi)放尋址法

  #include<iostream>
  #include<cstring>using namespace std;const int N=200003,null=0x3f3f3f3f;  //N數(shù)組長(zhǎng)度一般為數(shù)據(jù)范圍的2~3倍且為質(zhì)數(shù)，null表示空指針
  int h[N]; //h表示槽的位置
  int n;// 如果x在哈希表中，返回x的下標(biāo)；如果x不在哈希表中，返回x應(yīng)該插入的位置
  int find(int x)
  {int k = (x % N + N) % N;  //函數(shù)映射到槽上while (h[k] != null && h[k] != x)  //這個(gè)槽里面有數(shù)，并且·這個(gè)數(shù)不是我，循環(huán)繼續(xù){k ++ ;  //找下一個(gè)槽if (k == N) k = 0;  //如果找到最后了，返回0，繼續(xù)尋找}return t;
  }int main()
  {scanf("%d",&n);memset(h,0x3f,sizeof h);while(n--){char op[2];int x;scanf("%s%d",op,&x);int k=find(x);if(*op=='I') h[k]=x;  //往哈希表里面插入元素else{if(h[k]!=null) puts("Yes");  //在哈希表里面尋找元素else puts("No");}}return 0;
  }
  

4.字符串哈希

字符串哈希是字符串到數(shù)字的映射關(guān)系。

我認(rèn)為這個(gè)記住模板就行。

• 映射

  • 我們使用的映射關(guān)系是字符串到P進(jìn)制數(shù)的映射關(guān)系（P是任意的），保證映射是一一對(duì)應(yīng)的，不能有沖突。
  • 使沖突最小化，我們?nèi)?code>P=131 或者 P=13331 ，并且把字符串映射到 $2^{64}$ 范圍內(nèi)的數(shù)字

• 操作

  1. 先預(yù)處理出來(lái)，字符串所有前綴的哈希

     
     防止沖突，不能映射成0。

  2. 求一段區(qū)間的哈希值

     

  3. 哈希映射的時(shí)候，要對(duì)數(shù)值取N的模，unsigned long long 的范圍就是$2^{64}$ ，我們可以用它來(lái)巧妙地解決取模，因?yàn)檎?超過(guò) unsigned long long 就會(huì)溢出。

• 代碼模板

  typedef unsigned long long ULL;
  ULL h[N], p[N]; // h[k]存儲(chǔ)字符串前k個(gè)字母的哈希值, p[k]存儲(chǔ) P^k mod 2^64// 初始化
  p[0] = 1;
  for (int i = 1; i <= n; i ++ )
  {h[i] = h[i - 1] * P + str[i];p[i] = p[i - 1] * P;
  }// 計(jì)算子串 str[l ~ r] 的哈希值
  ULL get(int l, int r)
  {return h[r] - h[l - 1] * p[r - l + 1];
  }
  

• 例題

  給定一個(gè)長(zhǎng)度為 n 的字符串，再給定 m 個(gè)詢問(wèn)，每個(gè)詢問(wèn)包含四個(gè)整數(shù) l1,r1,l2,r2，請(qǐng)你判斷 [ l1 , r1 ] 和 [l2,r2]這兩個(gè)區(qū)間所包含的字符串子串是否完全相同。

  字符串中只包含大小寫(xiě)英文字母和數(shù)字。

  輸入格式

  第一行包含整數(shù) n 和 m，表示字符串長(zhǎng)度和詢問(wèn)次數(shù)。

  第二行包含一個(gè)長(zhǎng)度為 n 的字符串，字符串中只包含大小寫(xiě)英文字母和數(shù)字。

  接下來(lái) m 行，每行包含四個(gè)整數(shù) l1,r1,l2,r2，表示一次詢問(wèn)所涉及的兩個(gè)區(qū)間。

  注意，字符串的位置從 1 開(kāi)始編號(hào)。

  輸出格式

  對(duì)于每個(gè)詢問(wèn)輸出一個(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
  

  #include<bits/stdc++.h>
  using namespace std;typedef unsigned long long ULL;  //ULL代替取模，映射哈希函數(shù)const int N=100010,P=131;
  ULL p[N],h[N];   //p表示前綴哈希，h表示哈希值int n,m;
  char str[N];ULL get(int l,int r)  //求某段區(qū)間的哈希值
  {return  h[r]-h[l-1]*p[r-l+1];  //右端點(diǎn)的前綴哈希值-左端-1的前綴和哈希值*區(qū)間進(jìn)制
  }int main()
  {scanf("%d%d%s",&n,&m,str+1);  //預(yù)處理，直接從str+1 開(kāi)始輸入（后面涉及-1操作）p[0]=1;  //初始化，因?yàn)楹竺嫔婕?1和乘法for(int i=1;i<=n;i++){p[i]=p[i-1]*P;  //哈希映射，P進(jìn)制h[i]=h[i-1]*P+str[i];  //前綴哈希值}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");  //區(qū)間哈希值相等，則區(qū)間的字符相等else puts("No");}return 0;
  }
  

  之后補(bǔ)充 STL 中哈希表用法