哈希笔记
fengqiao17 · · 个人记录
1. 哈希基础
hash 算法其实用通俗的语言来说就是把字符串（或其他）用某种方法转换为一个数字，方便进行比较。这种方法就叫做哈希函数，是可以自行设计的。转换出来的数字叫做哈希值，通常是用来比较。
2. 哈希函数设计
一般是用以下步骤：
- 将字符串（或其他）一位一位地转换为一个
base进制的数，其中的进制数base可以自行选取； - 由于转换出来的数可能较大，所以我们还需要取模。这里的模数有些讲究，尽量选取质数作为模数，例如
998244353或者10^6 + 7 都可以。
3. 哈希冲突
可以注意到，在我们最后取模时，有一些原本不相同的数会有相同的哈希值，这种情况就叫做哈希冲突。
解决方法有以下几种：
- 自然溢出
我们可以把所有的变量都开成 unsigned long long，这样就相当于模了一个
- 双哈希
我们设计两个哈希函数，相当于每个字符串都有两个身份，模数相当于两个的乘积，如果说上面一种还能构造，那么下一种几乎无敌。除非出题人对着你的模数出题，否则很难被卡。