哈希
我认为的哈希：
比较两个东西是否相同
把一个东西提前映射成一个数，像map，但是 O(1）比较
字符串哈希（进制哈希）
详解
https://www.luogu.com.cn/problem/P3370 第1题 字符串哈希 查看测评数据信息
如题，给定 N个字符串（第 i 个字符串长度为 Mi，字符串内包含数字、大小写字母，大小写敏感），请求出 N个字符串中共有多少个不同的字符串。
友情提醒：如果真的想好好练习哈希的话，请自觉。
N<=10000,每个字符串长度不会超过20
输入格式
第一行包含一个整数 N，为字符串的个数。
接下来 N 行每行包含一个字符串，为所提供的字符串。
输出格式
输出包含一行，包含一个整数，为不同的字符串个数。
输入/输出例子1
输入：
5
abc
aaaa
abc
abcc
12345
输出：
4
样例解释
无
板题
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e4+5;
const ull Base=131;
int n, ans=0;
ull h[N];
char s[N];
int main()
{
scanf("%d", &n);
for (int i=1; i<=n; i++)
{
scanf("%s", s+1);
for (int j=1; j<=strlen(s+1); j++)
h[i]=h[i]*Base+(ull)s[j];
}
sort(h+1, h+1+n);
ans=1;
for (int i=1; i<n; i++)
if (h[i]!=h[i+1]) ans++;
printf("%d", ans);
return 0;
}
字符串哈希，也是进制哈希，类似于把字符串映射成一个base进制数
步骤/解释：
1.取进制数(base):131, 1331，转换成base进制数，选这两个数冲突小到几乎无
2.映射的数太大会爆，要取模，余数当成哈希，通常模数p取一个大质数，不然容易冲突
技巧：自然溢出哈希，不用%p，映射出来的数定义成unsigned long long，会自爆，自动取模
3.双哈希，防止卡自爆，双重保险
取base1, base2, p1, p2，base代表进制，p代表模数，两个base必须不同，但是两个p可以相同
假设有字符串S1，字符串S2
我们取S1的a哈希值1（通过base1, p1计算）
再取S1的a哈希值2（通过base2, p2计算）
我们取S2的b哈希值1（通过base1, p1计算）
再取S2的b哈希值2（通过base2, p2计算）
a哈希值1==b哈希值1
a哈希值2==b哈希值2
才能判断S1=S2
矩阵哈希（二维哈希）
步骤/详解：
矩阵哈希：
1.处理行哈希（前缀和，递推）
2.处理每一行得到的哈希
对于步骤1，我们可以利用进制哈希来进行计算
对于步骤2，我们举个例
例如这个二维哈希，我们算出第一行的哈希值为h1后，再算第二行哈希值h2
我们想要把两行合并，也就是把第二行的值放第一行尾部
即1011 + 1110
也就是变成10111110
想要完成此操作，我们要先把第一行哈希乘上base^4，相当于再一次用了进制哈希，然后再加上第二行哈希
h1*base^4+h2
树哈希
详解：
要怎么算一棵数的哈希值呢？
以根节点为例：
算根节点的孩子哈希值，把根节点的哈希值和孩子的哈希值相加。
这个过程相当于不断dfs。
离散化
离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。这是百度百科上的定义。那么举个栗子，某个题目告诉你有1e5个数，每个数大小不超过1e9，要你对这些数进行操作（比如并查集之类的）。那么肯定不能直接开1e9大小的数组，但是1e5的范围就完全没问题。在举个栗子，现在对{4,7,6,9}进行离散化，那么得到的结果是{1,3,2,4}，也就是说，当我们并不需要这些数据具体是多少时，就只需要知道他们的相对大小就行了。
第一种， 先看一段代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int n, m=0, t[N], a[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],t[i]=a[i];
sort(t+1,t+n+1);
m=unique(t+1,t+n+1)-t-1;
for(int i=1;i<=n;i++)
a[i]=lower_bound(t+1,t+m+1,a[i])-t;
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
在这段代码中，a[]经过离散，范围就变成了m。
解释一下，unique是c++自带的一个函数，表示对一个数列去重，然后返回不重复的元素个数，当然在后面要减去首地址。
例如数组是{1,1,2,3,1}，那就会变成{1,2,3,1,1}，返回的m是3
那么这种离散化对于有重复元素的数列也可以适用，但复杂度相对后面要讲的第二种方法会高些。
大致步骤：对原数组排序，然后去重，再找在原数组中对应的大小
举个栗子：{6,8,4,9,5,6,7,4}，首先排序后得到{4,4,5,6,6,7,8,9}，去重{4,5,6,7,8,9}，然后原序列就变成了{3,5,1,6,2,3,4,1}。
第二种，复杂度比上面那一种要优，但不能处理重复元素。
先看代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
struct Node
{
int v,id;
bool operator < (const Node a)const
{
return v<a.v;//排序用
}
}a[N];
int n, rank[N];
int main()
{
cin>>n;
for (int i=1; i<=n; i++)
{
cin>>a[i].v;
a[i].id=i;
}
sort(a+1,a+n+1);
for (int i=1; i<=n; i++) rank[a[i].id]=i;
return 0;
}
这种方法直接用结构体存储原本的数列的元素的位置，然后排序以后将他们再重新赋值。那么rank[]就是结构体a[]离散化后的结果。
举个栗子：
v: 3 6 5 10 8
id:1 2 3 4 5
排序以后：
v: 3 5 6 8 10
id:1 3 2 5 4
所以离散化以后：
v: 3 5 6 8 10
id:1 3 2 5 4
rk:1 2 3 4 5（这里是按id来排，用代码理解其实就是取的 for (j: 1->n) rank[a[j].id]）
在按原来的顺序排列：
v: 3 6 5 10 8
rk:1 3 2 5 4
标签：进制,int,base,哈希,字符串,id From： https://www.cnblogs.com/didiao233/p/18310377