算法根本 -- 字符串哈希的原理与数值选定的分析

字符串哈希的原理与数值选定的分析

1. 什么是字符串哈希

字符串哈希（String Hashing）是一种用于快速比力字符串的技能，焦点头脑是：
将一个字符串 SSS 通过某种哈希函数转换为一个固定长度的整数（通常是一个较大的数模一个素数），然后用于字符串比力、搜索等场景。
应用场景：

  

• 字符串比力（比方，在字典或哈希表中查找字符串）  
  
• 字符串去重（比方，检测重复子串）  
  
• 子串匹配（比方，Rolling Hash 用于 Rabin-Karp 算法）  
  
• 字符串相似性检测（比方，用于数据去重或查找相似文本）
  

<hr> 2. 根本哈希函数：多项式哈希

最常用的字符串哈希方法是多项式哈希（Polynomial Hashing），公式如下：
H(S)=(S0⋅P0+S1⋅P1+S2⋅P2+...+Sn−1⋅Pn−1)mod  M H(S) = (S_0 \cdot P^0 + S_1 \cdot P^1 + S_2 \cdot P^2 + ... + S_{n-1} \cdot P^{n-1}) \mod M H(S)=(S0​⋅P0+S1​⋅P1+S2​⋅P2+...+Sn−1​⋅Pn−1)modM
此中：

  

• SiS_iSi​ 是字符串第 iii 个字符的 ASCII 码值（或其他数值映射）  
  
• PPP 是进制基数（Base）  
  
• MMM 是取模素数（Modulus）  
  
• nnn 是字符串长度
  

示例：
对于字符串 "abcd"，利用：

  

• P=31P = 31P=31  
  
• M=109+7M = 10^9+7M=109+7 （一个大素数）
  

盘算哈希值：
H("abcd")=(97⋅310+9