字符串-哈希

· · 算法·理论

先来讲点没用的个人废物经历

高二之后（具体是NOIP2022遗憾离场之后）就没再敲过OI了，一直在准备高考，高三真的是地狱级的痛苦，每天生不如死只能靠晚上回宿舍的漫画维持生活的最后一丝希望，写不完的作业和不会做的题扑面而来，也是体会到了中国式教育的巅峰。反正是坚持下来了（不坚持也没办法是吧

最后高考依托但是有lgu综评降大分然后就捞进来了

还是打算学计算机（Computer Science），可能可以吃点老本吧（

然后在计算机应用的基础上还是想搞点算法润色一下，就看到了ICPC，但想入校队的时候发现人早就满了（现在OI这么火了吗还真是），目前只能作为备用队队员参加，不过也是成功的组了个小队

小队成员都是外省来的佬，虽然都一年多没碰，但强度明显是大于我的（所以要抓紧复建啊啊啊啊

因为是团队赛，3人分工很重要，然后我就打算先搞字符串部分（其实是因为其他内容队员们都会然后我什么都忘了

所以下面步入正题吧

哈希 Hash

定义：将一个字符串映射到整数的函数f称为Hash函数

核心思想在于将字符串映射到一个比较小，方便比较的范围。

性质：

1.Hash函数值不一样时，两个字符串一定不一样；

2.Hash函数值一样时，两个函数不一定一样（尽量增加一样的几率）

多项式Hash

f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M

简明易懂呢（注意这里的s[i]指的是ASCII码数）

程序实现也非常简单，直接贴码

#define MOD 1000007 //可以根据数据范围调整
int get_hash(string s, int BASE)
{
    int l = s.size(), re = 0;
    for(int x = 0; x < l; x++) re = (re*BASE+int(s[x])) % MOD;
    return re;
}

函数名不能用hash，不然会CE！

然后这样的Hash函数是会比较容易出现哈希碰撞的，即a \neq b但f(a)=f(b)，这是我们非常不希望看到的

解决方案也很简单，生成多个不同base的Hash函数，只有所有函数值都相同的两个字符串才是真的相同，称为多值哈希

一般来说，两个Hash函数已经够用了，但实际上如果MOD之类调整不好可能会用更多，尤其是在数据范围很大的时候，建议用unsigned long long

OI-WIKI-哈希