hash（散列）——思想、編碼應用

散列

1，思想

引入：

直接把輸入的數作為數組的下标來對這個數的性質進行統計

但是如果輸入的範圍大于10^9或是字元串，就不能将它們直接作為數組下标了。

核心思想：

将元素通過一個函數轉為整數，使得該整數可以盡量唯一地代表這個元素。【這個函數就是散列函數】

即：如果一個元素在轉換前為key，那麼轉換後就是一個整數H（key）

對于key是整數的情況，常用的方法有：直接定址法、平方取中法、除留餘數法等

直接定址法就是直接把key作為數組下表，是最常用最實用的散列應用

或是線性變化（H(key)= a* key + b）

而平方取中法是取key的平方的中間若幹位作為hash值（很少用）；

除留餘數法是指把key除以一個數mod得到的餘數作為hash值的方法，

即H（key） = key % mod

通過這個散列函數，可以把很大的數轉換為不超過mod的函數，這樣就可以将它作為可行的數組小标（⚠️：表長TSize必須不小于mod，不然會産生越界）

顯然當mod是一個素數（質數）時，H（key）能盡可能覆寫[0,mod)範圍内的每一個數。

是以一般為了友善起見，取TSize是一個素數，而mod直接取成與TSize相等。

2，沖突

當除留餘數法産生兩個及以上的H（key）時，這種情況稱為“沖突”

解決沖突的方法：

1）線性探測法（Linear Probing）

當發生沖突時，檢查下一個位置H(key) + 1是否被占用，如果沒有就使用這個位置，否則繼續檢查下一個位置，直到找到一個可以使用過的位置，或者發現表中所有位置都已經被使用。（容易導緻紮堆——表中連續若幹位置都被使用）

2)平方探測法（Quadratic probing）

可以盡可能的避免紮堆現象，當表中下标為H（key）的位置被占時，将按下面的順序檢查表中的位置：

H（key）+ 1^2、H(key) - 1^2、H(key) + 2^2、H（key）-2^2、H（key）+3^2、…

若果檢查過程中H(key)超過了表長TSize,那麼就把H（key）+k^2對表長TSize取模；

若果檢查過程中出現H(key)-k^2<0的情況（假設表的首位為0），那麼将((H(key)-k^2)%TSize+TSize)%TSize作為結果（等價于将H(key)-k^2不斷加上TSize直到出現第一個非負數。

如果想避免負數的麻煩，可以隻進行正向的平方探測法。可以證明，如果k在[0,TSize]範圍内都無法找到位置，那麼當k>=TSzie，也一定無法找到位置

3)鍊位址法（拉鍊法）

鍊位址法不計算新的hash值，而是把所有的H（key）相同的key連接配接成一條單連結清單。

可以設定一個數組Link，範圍時Link[0]~Link[mod]，其中Link[k]存放H（key）= h的一條單連結清單，于是當多個關鍵字key的hash值都是h時，就可以直接把這些沖突的key直接用單連結清單連接配接起來，此時就可以便利這條單連結清單來尋找所有H（key）= h的key。

3，字元串hash初步

這裡重點在于讨論将一個字元串轉換為唯一的整數。

先假設字元串都是又大寫A～Z構成。不妨把A～Z視為0～25，這樣就把26個大寫字母對應到了二十六進制，這樣就可以按照二十六進制轉為十進制的思路，由進制轉化的結論可知，得到的十進制時唯一的，由此便可以實作将字元串映射為整數的需求（轉換為整數最大時26^len - 1, len為字元串長度）

int hashFunc(char S[], int len){

  int id = 0;

for (int i =0;i  < len; i++){

      Id = id * 26 +(S[i] - ‘A’);

    }

return id;

}      

⚠️：如果字元串S的長度比較長，那麼轉換成的整數也會很大，是以使用時len不能太長。

如果字元串中出現了小寫字母，那麼可以把A～Z作為0～25，而把a～z作為26～51，這樣就變成了五十二進制轉換為十進制的問題，做法相同。

int hashFunc(char S[], int len){

int id =0;

for (int i = 0; i < len ;i++){

     if(S[i] >= ‘A’ && S[i] <= ‘Z'){

      id = id*52 +(S[i] - ‘A’);

}else if(S[i] >= ‘a’ && S[i] <= ‘z’){

      id = id*52 +(S[i] - ’a’) + 26;

    }

  }

}      

而如果出現了數字，一般有兩種處理方法：

1）按照小寫字母的處理方法，增大進制到62

2）如果保證在字元串的末尾時确定個數的數字，那麼就可以把前面英文字母的部分按上面的思路轉化為整數，再将末尾的數字直接拼接上去。

例如：字元串“BCD4”，可以把“BCD”轉換為整數731，然後直接拼接上末尾的4變成7314即可。

示例代碼：

int hashFunc(chat s[], int len){

  int id;

  for (int i = 0; i < len - 1; ++i)

  {

    id = id * 26 + (S[i] - 'A'); 

  }

  id = id * 10 + (S[len - 1] - '0');

  return id;

}      

練習題目：

給出N個字元串，再給出M個查詢字元串，問每個查詢字元串子在N個字元串出現的次數。

#include<cstdio>

const int maxn = 100;

char S[maxn][5];

char temp[5];

int hastTable[26 * 26 * 26 +10];



int hashFunc(char S[], int len){

  int id = 0;

  for (int i = 0; i < len; ++i)

  {

    id = id * 26 + (S[i] - 'A');

  }

  return id;

}



int main(int argc, char const *argv[])

{

  int n, m;

  scanf("%d%d", &n, &m);

  for (int i = 0; i < n; ++i)

  {

    scanf("%s",S[i]);

    int id= hashFunc(S[i], 3);

    hastTable[id]++;

  }



  for (int i = 0; i < m; ++i)

  {

    scanf("%s", temp);

    int id = hashFunc(temp, 3);

    printf("%d\n", hastTable[id]);

  }

  return 0;

}