字符串哈希的基本概念和數學原理分析

1. 字符串哈希的定義和基本概念

哈希函數的定義

哈希函數（Hash Function）是一種將任意長度的輸入映射為固定長度輸出的函數。對于字符串而言，哈希函數通過某種算法將字符串轉換成一個整數，該整數稱為哈希值。良好的哈希函數通常具有以下特性：

• 確定性（Deterministic）：相同的輸入必須產生相同的哈希值。
• 均勻分布（Uniformity）：不同輸入的哈希值應盡可能均勻分布，避免哈希沖突（不同輸入產生相同哈希值）。

字符串哈希的作用

將字符串轉換為哈希值，可以顯著提升字符串比較和查找的效率。例如，在字符串匹配算法 Rabin-Karp 中，哈希值可以用于快速篩選可能匹配的位置，從而減少逐字符比較的次數。

哈希沖突及其處理

由于哈希函數將龐大的輸入空間映射到有限的輸出空間，不可避免地會發生哈希沖突（Collision）。即，可能存在 Hash(S) = Hash(T)，但 S ≠ T。

解決哈希沖突的方法：

• 數據結構層面（哈希表）：
  • 開鏈法：使用鏈表存儲沖突元素。
  • 開放地址法：在哈希沖突時尋找下一個可用槽位（線性探測、二次探測、雙重哈希）。
• 字符串算法層面：
  • 雙哈希（Double Hashing）：使用兩個不同的哈希函數，只有兩個哈希值都相等時才認為字符串相等。
  • 增大哈希空間：選取更大的模數 $M$ 以減少沖突概率。
  • 最終驗證：在哈希值相等時進行字符串逐字符比對。

---

2. 字符串哈希的數學原理

多項式哈希（Polynomial Hashing）

字符串哈希常用的方法之一是多項式哈希，其基本思想是將字符串視為某個進制的數，并進行模運算。形式化定義如下：

$$H(S)=(s_1\times B^{n?1}+s_2\times B^{n?2}+?+s_n\times B^0)\mathrm{mod}M.$$

其中：

• $s_i$：第 $i$ 個字符的數值（如 ASCII 編碼）。
• $B$：基數（通常選 31、131、13331 等）。
• $M$：模數（通常選大質數，如 $10^9+7$）。

示例：
對于字符串 "abcde"，假設 a=1, b=2, ..., e=5，且 $B=31$，則：
$$H("abcde")=(1\times 31^4+2\times 31^3+3\times 31^2+4\times 31^1+5\times 31^0)\mathrm{mod}M.$$

基數 $B$ 和模數 $M$ 的選擇

• 模數 $M$：
  • 應選大質數，以減少哈希沖突，如 $10^9+7$。
  • 也可選 $2^{64}$ 直接利用整數溢出（非質數）。
• 基數 $B$：
  • 通常選取比字符集大小更大的質數，如 31、131、13331。
  • 選質數可減少哈希值模式性，提高均勻分布性。

滾動哈希（Rolling Hash）

滾動哈希是一種在 $O(1)$ 時間計算滑動窗口子串哈希的方法，推導如下：

設 $H(i)$ 表示 S[i:i+m-1] 的哈希值：
$$H(i)=(s_i\times B^{m?1}+s_{i+1}\times B^{m?2}+?+s_{i+m?1}\times B^0)\mathrm{mod}M.$$

計算 $H(i+1)$ 時，可由 $H(i)$ 推導：
$$H(i+1)=(H(i)\times B?s_i\times B^m+s_{i+m})\mathrm{mod}M.$$

該方法避免了重新計算每個子串的哈希值，大幅提升效率。

---

3. 字符串哈希的常見算法

Rabin-Karp 算法

Rabin-Karp 通過滑動窗口 + 哈希匹配實現高效字符串查找：

1. 計算模式串 $P$ 的哈希值 $H(P)$。
2. 在文本串中滑動窗口計算每個子串哈希值 $H_T(i)$。
3. 若 $H_T(i)=H(P)$，則進一步驗證字符串是否完全匹配。

時間復雜度分析

• 樸素匹配算法：$O(nm)$
• Rabin-Karp：
  • 預處理模式串：$O(m)$
  • 計算 $n?m+1$ 個子串哈希：$O(n)$
  • 平均復雜度 $O(n+m)$，最壞情況下（哈希沖突過多）$O(nm)$。

---

4. 字符串哈希的時間與空間復雜度

操作	樸素方法	哈希方法
單次字符串比較	$O(n)$	$O(1)$
查找子串	$O(nm)$	$O(n+m)$（Rabin-Karp）
哈希計算	$O(n)$	$O(n)$
滾動哈希更新	$O(nm)$	$O(n)$
哈希表查找	$O(n)$	$O(1)$（均攤）

---

5. 字符串哈希的應用場景

字符串匹配

• 單模式匹配：Rabin-Karp 算法。
• 多模式匹配：對多個模式串建立哈希表。

重復字符串檢測

• 大數據集合查重：Bloom Filter 結合哈希可快速去重。
• 文檔查重：對固定長度子串進行哈希比對。

哈希索引（數據存儲）

• 哈希表（Hash Table）：字符串鍵值存儲，如 Python dict。
• 數據庫索引：MySQL 等數據庫采用哈希索引加速查詢。

數據完整性校驗

• 文件哈希（MD5、SHA-256）：用于數據校驗、防止篡改。
• Git 版本管理：Git 采用 SHA-1 哈希標識文件版本。

分布式系統

• 一致性哈希：用于負載均衡，如緩存服務器的分片管理。
• DHT（分布式哈希表）：用于 P2P 網絡中的數據存儲。

---

總結

字符串哈希是一種強大且高效的字符串處理技術，廣泛應用于字符串匹配、查重、數據存儲和分布式計算等領域。合理選擇哈希函數的參數（如基數 $B$ 和模數 $M$），并結合滾動哈希和雙重哈希等技術，可以大幅提升字符串處理的性能，并降低哈希沖突帶來的影響。

---