哈希

字符串的存储

当我们存储一个字符串，考虑如何将他对那个到内存中呢？还有一个条件，你需要需要实现快速进行字符串比较。

你可能会想到一下几种方式：

1. 按位存储：

你开一个长度为 $5$ 的 char 数组，然后把 hello 挨个字符存进去。

那么现在问题来了，如果我现在给你一个字符串，长度为 $2\times 10^5$，显然你也是可以存下来的，但是你存下来以后，我又给了你一个 $2\times 10^5$ 个字符的串，叫你判断这两个串是不是一样的，好嘛，你得从第一位开始比对，如果比到不一样的还好，就可以直接 break 掉，但是如果一直没比到不一样的，你就得比到最后一位，这样的计算量是恐怖的。

2. 编号存储：

你可以对每种字符进行编号，比如我们就以长度为三，以 a、b、c 组成的字符串为例，可能有 aaa，aab，aac，aba，abb，abc，aca，acb，acc，baa，bab，bac，bba，bbb，bbc，bca，bcb，bcc，caa，cab，cac，cba，cbb，cbc，cca，ccb，ccc 共 $3^3=27$ 种，然后我们把他们按照 $1\sim 27$ 进行编号，那么我们来了一个 abc，它就对应为 $6$，来了一个 cca，它对应的就是 $25$。

你可能觉得这样存储很好，可以快速地比较很多字符串，但是考虑一个问题，刚才举的是三个字符，长度为三的字符串的例子，如果下面这个例子呢？

你们班有 50 个同学，每个人的名字都是三个字，且互不相同，中国汉字假如有 $5000$ 个（实际可能更多），那么每个人的名字都有 $5000^3=1.25\times 10^{11}$ 种可能，你显然不能把所有可能的名字都搞出来，然后进行编号，比如我们把“李小一”设置为 $1$，“王小二”设为 $2$，这样一直下去，那么你需要一个可怕的对用系统，然后从你的对应系统中，再去找每个人的名字，这是很麻烦的，但你实际上只需要存 $50$ 个人的名字就可以了中国有一个成语，叫九牛一毛，这个成语都不够夸张，因为我不相信九头牛身上能有 $1.25\times 10^{11}$ 根毛。

更抽象的，如果你要存长度为 $10^5$ 的中文字符串，亦或者假如你要存储的是“算法导论”这本书，你去搞他的所有情况，这将是恐怖的事情，那么问题就来了：

那么我们需要一个对应系统，能把你的字符串对应起来，并且可以快速比较，如何实现呢？

考虑一个 built-in type，也就是系统内置的数据类型，举个例子，比如 int 或者 long long，比较它们想必是非常方便的，复杂度也是 $O(1)$ 的，所以我们需要一种方式，把字符串进行与 int 对应，但是不能采取刚才那种把所有可能情况都编号的笨蛋方法。

hash

哈希就是解决这个问题的最好方法，他的理念在于模运算和概率问题，考虑将一个纯英语小写字符串存储为 26 进制数，比如 hello 这个字符串，就可以对应为：$(74BBE)_{26}$，那么，我们就将 hello 转为了一个数字，这个数字的十进制大家可以自己转化一下，我算出来是 $3276872$。

如果我们存储一个比较长的单词，比如 goodluckcspandnoip，那么算出他的结果是一个超过 long long 范围的数字，这个时候，我们把它存储下来，需要高精度，那么如果存储一个长度为 $10^5$ 级别的字符串，需要一个长度为 $26^{(10^5)}$ 的别的数组来存这个高精度数，仍然没有任何效果。

考虑通过牺牲的方式来辅助运算，那么，如果我们把每次的二十六进制数还是用十进制数表示，但是我们始终保持在 int/long long 范围内，可以通过对一个与 int/long long 范围相近的质数取模的方式来实现，比如：

const int mod = 1e9+7;
void hash(string s,long long a[]) {
    for(int i=0;i<s.size();++i) {
        a[i+1]=a[i]*29+s[i]-'a';
        a[i+1]%mod;
    }
}

hash 冲突

这样做有一定的风险，因为我们得到的是一个长度小于 $10^9+7$ 的数字，而且对应数字相同不一定代表同样的子串，比如可以通过特殊构造构造出 hash 值相同而又互不相同的字符串，这种情况我们成为 hash 冲突，因此，提出几点建议：

1. 模数要尽可能大，最好在 $10^{16}$ 级别（更大会炸 long long，小了）；
2. 乘数不要选择 $26$，因为 $26$ 不是质数，更容易冲突，如果是小写字母可以是 $29$，如果是小写，大写和数字结合可以用 $131$；

比较保险的写法：自然溢出！

刚才讲到，如果模数很大，会造成 long long overflow，所以建议在 $10^{16}$ 级别，那么，有没有一种方法，可以让模数更大一些呢？

考虑如果 int 超出了范围，会变成负数，那么 unsigned int 呢，如果给一个值域为 $[0,2^{32}-1]$ 的 unsigned int 赋值为 $2^{32}$ 它就会变成 $0$，若赋值为 $k\times 2^{32}+p\ (k\in Z,\ p\in[0,2^{32}-1])$ 它就会变成 $p$，这就实现了一种对于 $2^{32}$ 取模的效果，如果换成 unsigned long long，就可以做到对于 $2^64$ 取模的效果，众所周知，$2^{64}-1\approx 2\times 10^{19}$，非常保险，这种做法，实际利用的就是 unsigned 的 overflow，所以叫做自然溢出。

习题练习

CF113B Petr#
CF514C Watto and Mechanism
AT_abc284F ABCBAC