“十分简单易懂的字符串哈希教程”
字符串哈希
0x01.什么是哈希
定义(摘自OI wiki)[https://oi-wiki.org/string/hash/]>
我们定义一个把字符串映射到整数的函数 f，这个 f 称为是 Hash 函数。
我们希望这个函数 f 可以方便地帮我们判断两个字符串是否相等。
人话：
把字符串以特定的方式表示为一串数，可以直接通过比较这一串数来判断字符串是否（相等/不同）。
0x02.为什么要哈希
——复杂度优化
我们记字符串长度为L，显然，直接比较是O(L)的，但如果将字符串以特定的方式映射为整数，那么就可以O(1)比较，大大节约了时间（祖传空间换时间awa）
0x03.“特定的方式”
我们不妨用S[i]表示字符串的各位字符，A(x)表示字符x对应的ASCII值
十分粗糙与简陋的思路：
容易想到将A(S[i])乘以一个正整数(Base)，再将各位加起来。
hash+=s[i]*Base
太弱了
Hack:对于任意A(S[m])+A(S[n])=A(S[i])的，甚至只需要相同字符，排列方式不同的字符串都能使上述哈希失去正确性。这种情况我们称其为哈希冲突