哈希和字符串哈希

哈希（Hash）

Hash 表

Hash 表又稱為散列表，一般由 Hash 函數（散列函數）與鏈表結構共同實現。與離散化思想類似，當我們要對若干復雜信息進行統計時，可以用 Hash 函數把這些復雜信息映射到一個容易維護的值域內。因為值域變簡單、范圍變小，有可能造成兩個不同的原始信息被 Hash函映射為相同的值，所以我們需要處理這種?沖突?情況。有一種稱“開散列”的解決方案是，建立一個鄰接表結構，以 Hash 函的值域作為表頭數組 head，映射后的值相同的原始信息被分到同一類，構成一個鏈表接在對應的表頭之后，鏈表的節點上可以保存原始信息和一些統計數據。

Hash 表主要包括兩個基本操作:

計算 Hash 函數的值。
定位到對應鏈表中依次遍歷、比較。

無論是檢查任意一個給定的原始信息在 Hash 表中是否存在，還是更新它在 Hash 表中的統計數據，都需要基于這兩個基本操作進行。當 Hash 函數設計較好時，原始信息會被?比較均勻地?分配到各個表頭之后，從而使每次查找、統計的時間降低到“原始信息總數除以表頭數組長度”。若原始信息總數與表頭數組長度都是?O(N)O(N)?級別且 Hash 函數分散均勻，幾乎不產生沖突，那么每次查找、統計的時間復雜度期望為?O(1)O(1)?。

例如，我們要在一個長度為?NN?的隨機整數序列?AA?中統計每個數出現了多少次。可以設計 Hash 函數為?H(x)=(xmodP)+1H(x)=(xmodP)+1?其中?PP?是個比較大的質數但不超過?NN?。顯然，這個 Hash 函數把數列?AA?分成?PP?類，我們可以依次考慮數列中的每個數?A[i]A[i]?，定位到?head[H(A[i])]head[H(A[i])]?這個表頭所指向的鏈表。如果該鏈表中不包含?A[i]A[i]?我們就在表頭后插入一個新節點?A[i]A[i]?，并在該節點上記錄?A[i]A[i]?出了?11?次，否則我們就直接找到已經存在的?A[i]A[i]?節點將其出現次加?11?。因為整數序列?AA?是隨機的，所以最終所有的?A[i]A[i]?會比較均地分散在各個表頭之后，整個算法的時間復雜度可以近
似達到?O(N)O(N)?。

上面的例子是一個非常簡單的 Hash 表的直觀應用。對于非隨機的數列，我們可能需要設計更好的 Hash 函數來保證其時間復度。同樣地，如果我們需要維護的是比大整數復雜得多的信息的某些性質(如是否存在、出現次數等)，也可以用 Hash 來解決。字符串就是一種比較一般化的信息，在本節的后半部分，我們將會介紹一個競賽中極其常用的字符串 Hash 算法。

例題1：?P6486 雪花雪花雪花 - TopsCoding

定義 Hash 函數?H(ai,1,ai,2,...,ai,6)=(∑j=16ai,j+∏j=16ai,j)modPH(ai,1?,ai,2?,...,ai,6?)=(∑j=16?ai,j?+∏j=16?ai,j?)modP?，其中?PP?是我們自己選取的一個較大的質數。顯然，對于兩片形狀相同的雪花，它們六個角的長度之和、長度之積都相等，因此它們的 Hash 函數值也相等。

建立一個 Hash 表，把?nn?片雪花依次插入。對于每片雪花?ai,1,ai,2,...,ai,6ai,1?,ai,2?,...,ai,6??，我們直接掃描表頭?H(ai,1,ai,2,...,ai,6)H(ai,1?,ai,2?,...,ai,6?)?對應的鏈表，檢查是否存在與?ai,1,ai,2,...,ai,6ai,1?,ai,2?,...,ai,6??形狀相同的雪花即可。對于隨機數據，期望的時間復雜度為?O((N/P)2N)O((N/P)2N)?；取?PP?為最接近?NN?的質數，期望的時間復雜度為?O(N)O(N)?。在下一節中，我們將學習循環同構串的“最小表示法”，進一步提高判斷兩片雪花形狀是否相同的效率。

問題1：設計哈希函數時，一定要對素數取模嗎？

回答1：不一定，看你對什么數據hash，以及要用來干什么。假如哈希的對象是隨機均勻分布的，那么無論模數取什么，哈希后的分布仍會是均勻的，也就無所謂一定要模質數。但在實際中往往關鍵字有某種規律，例如大量的等差數列，那么公差和模數不互質的時候發生碰撞的概率會變大，而用質數就可以很大程度上回避這個問題。因此，我們往往會讓模數是一個大質數。

參考代碼：

const int N = 100006, P = 99991;
int n, a[6], b[6];
struct Snow {  // 雪花int s[6];
};
vector<Snow> snow[N];  // 哈希表int H() {  // 哈希函數int s = 0, k = 1;for(int i = 0; i < 6; i++) {(s += a[i]) %= P;k = (long long)k * a[i] % P;}return (s + k) % P;
}bool pd() {for(int i = 0; i < 6; i++)for(int j = 0; j < 6; j++) {bool flag = 1;for(int k = 0; k < 6; k++)if(a[(i+k)%6] != b[(j+k)%6]) {flag = 0;break;}if (flag) return 1;flag = 1;for(int k = 0; k < 6; k++) {if(a[(i+k)%6] != b[(j-k+6)%6]) {flag = 0;break;}}if(flag) return 1;}return 0;
}bool insert() {int h = H();for(auto c : snow[h]) {memcpy(b, c.s, sizeof b);if(pd()) return 1;}Snow s;memcpy(s.s, a, sizeof s.s);snow[h].push_back(s);return 0;
}int main() {cin >> n;for(int i = 1; i <= n; i++) {for (int j = 0; j < 6; j++) cin >> a[j];if(insert()) {cout << "Twin snowflakes found.";return 0;}}cout << "No two snowflakes are alike.";return 0;
}

例題2：?P6224 合肥市2022初中組牛了個牛 - TopsCoding

對異或的性質敏感的同學可以看出本題如果采用前綴區間異或去計算會比較簡潔，但是如果直接做異或，會有問題，可能出現?a?b=c?da?b=c?d?的情況。于是我們可以考慮把輸入的數字從值域?[1,n][1,n]?哈希后映射到一個更大的值域上之后，再做前綴異或，這樣出現?a?b=c?da?b=c?d?的概率就會極大降低。

如果還是擔心一次哈希后會出現上面的情況，那么可以換一個模數，再對原數組做一次哈希，如此概率就會更低。這樣的處理方式叫做雙哈希，是一種常見的避免哈希沖突的處理方式。

字符串哈希

有時，我們要對字符串進行查找，這時，可能會用到字符串哈希的技巧。

下面介紹的字符串 Hash 函數把一個任意長度的字符串映射成一個非負整數，并且其沖突概率幾乎為?00?。

取一固定值?PP?，把字符串看作?PP?進制數，并分配一個大于?00?的數值，代表每種字符。一般來說，我們分配的數值都遠小于?PP?。例如，對于小寫字母構成的字符串，可以令?a=1,b=2,...,z=26a=1,b=2,...,z=26?。取一固定值?MM?，求出該?PP?進制數對?MM?的余數作為該字符串的 Hash 值。

一般來說，我們取?P=131P=131?或?P=13331P=13331?此時?HashHash?值產沖突的率極低，只要 Hash 值相同，我們就可以認為原字符串是相等的。通常我們取?M=264M=264?，即直接使用 unsigned long long 類型存儲這個 Hash 值，在計算時不處理算術溢出問題，產生
溢出時相當于自動對?264264?取，這樣可以避免低效的取模(?modmod?) 運算。

除了在極特殊構造的數據上，上述 Hash 算法很難產生沖突，一般情況下上述 Hash算法完全可以出現在題目的標準解答中。我們還可以多取一些恰當的?PP?和?MM?值(例如大質數)，多進行幾組 Hash 運算，當結果都相同時才認為原字符串相等，就更加難
以構造出使這個 Hash 產生錯誤的數據。

對字符串的各種操作，都可以直接對?PP?進制數進行算術運算反映到 Hash 值上。

構造字符串哈希?：如果我們已知字符串?SS?的 Hash 為?H(S)H(S)?，那在?SS?后添加一個字符?cc?構成的新字符串?S+cS+c?的 Hash 值就是?H(S+c)=(H(S)?P+value[c])modMH(S+c)=(H(S)?P+value[c])modM?，其中乘?PP?就相當于?PP?進制下的左移運算，?value[c]value[c]?是我們為?cc?選定的代表數值。
取子串哈希值?：如果我們已知字符串?SS?的 Hash 值為?H(S)H(S)?，字符串?S+TS+T?的 Hash 值為?H(S+T)H(S+T)?，那么字符串?TT?的 Hash 值?H(T)=(H(S+T)?H(S)?Plength(T))modMH(T)=(H(S+T)?H(S)?Plength(T))modM?。這就相當于通過?PP?進制下在?SS?后邊補?00?的方式把?SS?左移到與?S+TS+T?的左端對齊，然后二者相減就得到了?H(T)H(T)?。

例如，?S=S=?abc，?c=c=?d，?T=T=?xyz，則：

SS?表示?PP?進制數：?1?2?31?2?3

H(S)=1?P2+2?P+3H(S)=1?P2+2?P+3

H(S+c)=1?P3+2?P2+3?P+4=H(S)?P+4H(S+c)=1?P3+2?P2+3?P+4=H(S)?P+4

S+TS+T?表示為?PP?進制數：?1?2?3?24?25?261?2?3?24?25?26

H(S+T)=1?p5+2?p4+3?p3+24?p2+25?p+26H(S+T)=1?p5+2?p4+3?p3+24?p2+25?p+26

SS?在?PP?進制下左移?length(T)length(T)?位：?1?2?3?0?0?01?2?3?0?0?0

二者相減就是?TT?表示為?PP?進制數：?24?25?2624?25?26

H(T)=H(S+T)?(1?P2+2?P+3)?P3=24?P2+25?P+26H(T)=H(S+T)?(1?P2+2?P+3)?P3=24?P2+25?P+26

根據上面兩種操作，我們可以通過?O(N)O(N)?的時間預處理符所有前綴 Hash 值并在?O(1)O(1)?的時間內查詢它的任意子串的 Hash 值。

問題2：如果兩個字符串明明不相等，但他們取模后的結果相等，這個概率有多大？

回答2：把這個問題換一種問法: 給你?nn?個字符串，出現兩個字符串明明不相等，他們對應的數字模?PP?卻相等的概率超過?50%50%?的可能性有多大? 這就和我們之前學過的生日悖論完全一致了！這里可以直接給出結論——當?n>Pπ/2n>Pπ/2??時，概率就會超過?50%50%?。也就是說，當?nn?很大的時候，比如?nn?是?106106?級別的時候，模數至少要取到?10121012?才放心。但是在使用那么大的模數去進行運算的時候，會非常地不方便，所以一般情況下，我們直接利用?unsigned long long?的溢出來做取模運算，這樣效率還更高。

當然，我們也可以取兩個?109109?級別的質數來代替取一個?10181018?級別的質數，然后分別做哈希，分別比較。只有當兩種情況哈希值都相等的情況下，我們才認為原來的字符串相等。

為什么取兩個?109109?級別的質數就能代替一個?10181018?級別的質數呢? 這是因為，我們分別求出了兩種情況對應的進制數在模意義下的哈希值，那就可以用中國剩余定理還原成一個?0～10180～1018?的模意義下的取模后的值。

例題3：?P6487 兔子與兔子 - TopsCoding

屬于模板題，直接用上面的思路去處理即可。

參考代碼：

const int N = 1e6+5;
string s; 
int n, q;
unsigned long long f[N], p[N];  // 2^64 溢出 = 取模
int main() {ios::sync_with_stdio(0);cin.tie(0);cin >> s >> q;n = s.size();p[0] = 1; // 131^0for (int i = 1; i <= n; i++) {f[i] = f[i-1] * 131 + (s[i-1]-'a'+1); // 前 1~i 個字符的前綴哈希值p[i] = p[i-1] * 131;                  // 131 進制下的 131^i，用于計算區間哈希值}for (int i = 1; i <= q; i++) {int l1, r1, l2, r2;cin >> l1 >> r1 >> l2 >> r2;if (f[r1] - f[l1-1] * p[r1-l1+1] == // l1~r1 的哈希f[r2] - f[l2-1] * p[r2-l2+1]) { // l2~r2 的哈希puts("Yes");} else {puts("No");}}
}

例題4：?P6488 最長的回文子串（Palindrome） - TopsCoding

我們知道，回文子串有兩種：長度是奇數的和長度是偶數的。

于是在本題中，我們可以枚舉?SS?的回文子串的中心位置?ii?，看從這個中心位置出發向左右兩側最長可以擴展出多長的回文串。也就是說：

奇數長度的：求出一個最大的整?pp?使得?S[i?p～i]=reverse(S[i～i+p])S[i?p～i]=reverse(S[i～i+p])?，那么以?ii?為中心的最長奇回文子的長度就是?2?p+12?p+1?。
偶數長度的：求出一個最大的整數?qq?使得?S[i?q～i?1]=reverse(S[i～i+q])S[i?q～i?1]=reverse(S[i～i+q])?，那么以?i?1i?1?和?ii?之間的夾縫為中心的文子的度就是?2?q2?q?。

根據上一道題目，我們已經知道在?O(N)O(N)?預處理前綴 Hash 值后，可以?O(1)O(1)?計算任意子串的 Hash 值。類似地，我們可以著做一預處理，就可以?O(1)O(1)?計算任意子串倒著讀的 Hash 值。于是我們可以對?pp?和?qq?進行二分答案查找。用 Hash?O(1)O(1)?比較一個正著讀的子串和一個倒著讀的子串是否相等，從而在?O(log?N)O(logN)?時間內求出最大的?pp?和?qq?。在枚舉過的所有中心位置對應的奇偶回文子串長度中取 max 就是整道題目的答案，時間復雜度為?O(Nlog?N)O(NlogN)?。

有一個名為 Manacher 的算法可以?O(N)O(N)?解該問題，感興趣的讀者可以自行查閱相關資料，推薦閱讀?Manacher - OI Wiki (oi-wiki.org)。