字符串之Hash
0x01 进制Hash`
众所众知我们比较字符串是需要 \(\mathcal{O}(len)\) 的时间，但数字只需要 \(\mathcal{O}(1)\) 即可比较。所以有没有方法可以吧字符串变成数字呢？
肯定有啊！那就是进制Hash了。啥是进制Hash呢？进制Hash顾名思义就是吧字符串看成 \(b\) 进制数。\(b\) 一般为 \(131,13131\)。
进制Hash有两种实现：
- 左为低位，右为高位
code:
int gethash(string s){int hash=0;for(int i=0,b=1;i<len;i++,b*=B){hash+=s[i]*b;}return hash;
}
- 左为高位，右为低位
code:
int gethash(string s){int hash=0;for(int i=0;i<len;i++){hash=hash*B+s[i];}return hash;
}
本文以f2为例。
0x02模数
当然，这个数肯定会超long long所以我们一般还要模上一个 \(p\) 。\(p\) 一般为 \(998244353,10^9+7,10^9+9\) 或用unsigned long long（等于模 \(2^46\)）。因为某些原因请将 \(p\) 设为质数。
所以完整的code为
code:
int gethash(string s){int hash=0;for(int i=0;i<len;i++){hash=((hash*B)%P+s[i])%P;}return hash;
}
0x03 生日攻击
但是，这样可能会有两个不同的字符串Hash值相同这叫Hash冲突。那这个概率有多少呢？我们先开康康这个问题吧！
一个班上有 \(50\) 人，那没有两个人生日相同的概率为多少？（假定没有闰年，且每天出生的概率相同）
可以先自己想一想哦~
这是一个古典模型根据公式：\(P(A)=\frac{A}{N}\) 可以算出概率为 \(\frac{P^{50}_{365}}{2^{365}}<3%\)
这时有个结论，Hash冲突的概率为 \(e^{-\frac{n(n-1)}{2p}}\)
0x04 解决办法
那就是用大大大大模数或者用双Hash，也就是用不同的 \((b,p)\) 算出来的都一样就当相同。
0x05 截取&拼接
（此章以f2为例）
假设 \(S\) 的Hash为 \(H(s)\)， \(t\) 的Hash为 \(H(t)\)。
那显然 \(H(s+t)=b^{len_t}H(s)+H(t)\)
那拆分呢？对用前缀和。
我们可以从 \(H(s+t)=b^{len_t}H(s)+H(t)\) 得到 \(H(0...r)=b^{len_t}H(0...l-1)+H(l...r)\) 变形得 \(H(l..r)=H(0...r)-b^{r-l+1}H(0...l)\)