說到什么是字符串哈希(Hash)？很多人都會(huì)疑惑，我們可以這么理解，定義一個(gè)把字符串映射到整數(shù)的函數(shù) f，這個(gè) f 稱為是Hash函數(shù)。而我們希望這個(gè)函數(shù) f 可以方便地幫我們判斷兩個(gè)字符串是否相等。

（1）Hash 的思想

Hash 的核心思想在于，將輸入映射到一個(gè)值域較小、可以方便比較的范圍。

（2）使用場(chǎng)景

當(dāng)一個(gè)字符串規(guī)模很大，并且需要多次訪問該字符串或者子串的時(shí)候，我們可以用哈希函數(shù)對(duì)每個(gè)字符串進(jìn)行哈希，分別映射到不同的數(shù)字中去，即一個(gè)整數(shù)哈希值，然后我們可以根據(jù)哈希值找到需要的字符串。

（3）什么是哈希函數(shù)？

哈希函數(shù)是哈希的關(guān)鍵，首先理論上任何一個(gè)函數(shù)都能做哈希函數(shù)，但是在字符串哈希中，為了避免沖突采用了一種進(jìn)制哈希的方式（BKDRHash）。

原理：設(shè)定一個(gè)進(jìn)制P，需要計(jì)算一個(gè)字符串的哈希值時(shí)，把每個(gè)字符看成每個(gè)進(jìn)制位上的一個(gè)數(shù)字，這個(gè)串轉(zhuǎn)化成了一個(gè)基于進(jìn)制 P 的數(shù)，最后對(duì) M 取余數(shù)，就得到了這個(gè)字符串的哈希值。為簡(jiǎn)化計(jì)算可以取空間大小為 M=264是 unsigned long long 的長(zhǎng)度，一個(gè) unsigned long long 型的哈希值 H，當(dāng) H 值大于 M 時(shí)會(huì)自動(dòng)溢出，等價(jià)于自動(dòng)對(duì) M 取余，這樣能避免低效的取余運(yùn)算。

進(jìn)制 PPP 常用的值有31、131、1313、13131、131313等，用這些數(shù)值能有效避免碰撞。

例如計(jì)算只用小寫字母組成的字符串的哈希值，以 “abcabcabc”為例，令進(jìn)制 P=131：

直接把每個(gè)字符的 ASCII 碼看成代表它的數(shù)字，計(jì)算得：‘a(chǎn)’ * 131 ^2 + ‘b’ * 131 ^ 1 + ‘c’ * 131 ^ 0 = 1677554。

（4）如何實(shí)現(xiàn)求任意區(qū)間的哈希值

一般的我們對(duì)一個(gè)字符串的全部前綴進(jìn)行哈希值的計(jì)算，這樣我們就可以知道這個(gè)字符串任意連續(xù)子串的哈希值了。假設(shè)哈希前綴的值已經(jīng)求出，我們現(xiàn)在求區(qū)間【i ~ j】的哈希值就是 區(qū)間【0 ~ j】的哈希值 – 區(qū)間【0 ~ i】的哈希值 * p^ j – i + 1；

（5）計(jì)算字符串前綴的哈希值

利用前綴和公式即可

//h【i】的意義就是求區(qū)間【0~i】的字符串的哈希值
//we【i】 是記錄第i位字符的權(quán)值
for(int i = 1;i<=n;i++){
		h[i] = h[i - 1] * p + str[i];
		we[i] = we[i-1] * p;
	}

（6）字符串哈希代碼模板

typedef unsigned long long ULL;
ULL h[N], p[N]; 

// 初始化
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];
}
```cpp