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

🐾或許會很慢，但是不可以停下來🐾

1.定義

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

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

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

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

2.優(yōu)點

查找速度快

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

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

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

3.數(shù)字哈希

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

3.1拉鏈法

• 操作

  • 開一個一維數(shù)組來存儲哈希值；

  • 添加值（處理沖突）

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

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

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

    

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

    

  • 查找值

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

  • 刪除值

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

• 代碼實現(xiàn)

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

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

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

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

3.2開放尋址法

• 操作

  • 只開一個一維數(shù)組，數(shù)組的大小按經(jīng)驗來說一般是 數(shù)據(jù)范圍的2~3倍；
  • 先看一下，對應(yīng)的槽里有沒有數(shù)，有數(shù)的話，找下一槽，直到找到?jīng)]有數(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)  //這個槽里面有數(shù)，并且·這個數(shù)不是我，循環(huán)繼續(xù){k ++ ;  //找下一個槽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 說明哈希表里面沒有這個值

  • 刪除元素：

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

3.3 例題

維護一個集合，支持如下幾種操作：

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

現(xià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$
?$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;   //插在對應(yīng)槽的鏈表里面ne[idex]=h[k];h[k]=idex++;
  }bool find(int x)   //查找值的函數(shù)
  {int k=(x%N+N)%N;  //先找出對應(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];   //讀入一個字符的時候，直接用字符數(shù)組讀入，降低出錯率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;
  }
  

• 方法二：開放尋址法

  #include<iostream>
  #include<cstring>using namespace std;const int N=200003,null=0x3f3f3f3f;  //N數(shù)組長度一般為數(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)  //這個槽里面有數(shù)，并且·這個數(shù)不是我，循環(huán)繼續(xù){k ++ ;  //找下一個槽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)為這個記住模板就行。

• 映射

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

• 操作

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

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

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

     

  3. 哈希映射的時候，要對數(shù)值取N的模，unsigned long long 的范圍就是$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// 初始化
  p[0] = 1;
  for (int i = 1; i <= n; i ++ )
  {h[i] = h[i - 1] * P + str[i];p[i] = p[i - 1] * P;
  }// 計算子串 str[l ~ r] 的哈希值
  ULL get(int l, int r)
  {return h[r] - h[l - 1] * p[r - l + 1];
  }
  

• 例題

  給定一個長度為 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
  

  #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];  //右端點的前綴哈希值-左端-1的前綴和哈希值*區(qū)間進制
  }int main()
  {scanf("%d%d%s",&n,&m,str+1);  //預(yù)處理，直接從str+1 開始輸入（后面涉及-1操作）p[0]=1;  //初始化，因為后面涉及-1和乘法for(int i=1;i<=n;i++){p[i]=p[i-1]*P;  //哈希映射，P進制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;
  }
  

  之后補充 STL 中哈希表用法