哈希法(散列法)

哈希：一种映射关系
注意：一般int类型数据范围小用普通数组，数据范围大可以用unordered_map<int,int>

特殊的哈希情况：
1.double类型有精度问题，判断两个double是否相等：abs(a-b<1e-8)，故不能直接O(1)查看，只能O(n)遍历是否有相同值
2.string类型一般用字符串前缀哈希（p=131，unsigned long long）（一般不用unordered_map）

1.AcWing841.字符串哈希

字符串前缀哈希:用于匹配字符串

思路：
1.将字符串看做是p=131进制数，h[i]存的是前i个字符的哈希值（用秦九韶算法计算p进制）
2.w[i]存的是第i+1位的权值，即w[i]=p^i，最低位w[0]初始化为1（左边是高位，右边是低位）
3.用unsigned long long和质数p=131来保证几乎不会发生哈希冲突
4.get_hash(l,r)返回[l,r]字符的哈希值：h[r]-h[l-1]*w[r-l+1]

点击查看代码

2.AcWing 1402. 星空之夜

哈希表：每一个哈希值对应一种星群

思路：
1.先一个一个dfs遍历星群(连通块)，将连通块的所有点的坐标存入point数组
2.遍历结束后，point中两两坐标成对计算欧几里得距离，累加之和的double值即为当前星群的哈希值t(与方向无关)
3.如果t能在哈希表中找到，则为以前出现过的星群，反只则是新出现的星群，加入哈希表中
4.将当前星群涂色成哈希表对应的字符，然后找下一个星群重复以上操作

点击查看代码

3.AcWing 1221. 四平方和

哈希表

思路：
1.先双重循环枚举每个c和d，将(c*c+d*d)作为关键字，c和d的作为值存入哈希表中（哈希表中：h[c*c+d*d]={c,d}）
2.枚举a，b，然后在哈希表中找h[n-a*a-b*b]是否存在，存在则输出一次a,b,c,d即可退出
3.每一重循环时间复杂度为O(sqrt(n))，哈希时间复杂度为O(1),总的时间复杂度为O(n)

点击查看代码