算法 字元串Hash

解決問題：

      字元串hash主要應用在：在長度為n的主串S中比對長度為m的比對串T，傳回起始位置。

Hash的目的：

      通過字元串Hash函數把一個任意長度的字元串映射成一個非負整數，并且其沖突機率為零。

具體方法：

        取一固定值P，把字元串看作P進制數，并配置設定一個大于0的數值，代表每種字元。一般來說，我們配置設定的數值都遠小于P。取一固定值M，求出P進制數對M的餘數，作為該字元串的Hash值。

      一般來說，我們取P = 131 或 13331，此時Hash值産生沖突的機率極低，隻要Hash值相同，我們就可以認為原字元串是相等的。通常我們取M = 2 ^ 64，即直接使用unsigned long long 類型儲存這個Hash值，在計算時不處理算數溢出問題，産生的溢出相當于自動對 2 ^ 64取模。

具體運算：

      記字元串S的Hash值為H(S)，那麼在S後添加一個字元c構成的新字元串的 S + c 的Hash值H(S + c) = (H(S) * p + val[c]) mod M。val[c]為字元c的代表數值。

      同理去除字元串首位（最高位）H[S] = H[c + S] - val[c] * p ^ length(S);

不足之處：

      對于Hash值在0 ~ n之間均勻分布的Hash函數，出現不同字元串Hash值相等的期望步驟是O(sqrt(n))，在可以當作選取Hash函數的參考。

      同時為了及降低出現相同Hash值的機率，可以采取雙哈希來降低出現相同Hash值的機率，隻有兩個Hash值相等才認定字元串比對。如取：10 ^ 9 + 7 與 10 ^ 9 + 9。

代碼舉例：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
ULL base = 131;
int main(){
	string s;
	cin>>s;
	ULL res = 0;
	for(int i = 0; i < s.length(); i++){
		res = res * base + s[i] - 'a' + 1;
	}
	cout<<res;
}
           

參考：

leetcode-huwt

字元串hash-二喵君