字符串之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为例。

当然，这个数肯定会超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;
}

但是，这样可能会有两个不同的字符串Hash值相同这叫Hash冲突。那这个概率有多少呢？我们先开康康这个问题吧！

一个班上有 \(50\) 人，那没有两个人生日相同的概率为多少？（假定没有闰年，且每天出生的概率相同）

可以先自己想一想哦~

这是一个古典模型根据公式：\(P(A)=\frac{A}{N}\) 可以算出概率为 \(\frac{P^{50}_{365}}{2^{365}}<3%\)

这时有个结论，Hash冲突的概率为 \(e^{-\frac{n(n-1)}{2p}}\)

那就是用大大大大模数或者用双Hash，也就是用不同的 \((b,p)\) 算出来的都一样就当相同。

（此章以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)\)

编程学习学习日记实战经验

← 返回列表