今天是为算法写博客的第一天，在此暂且原谅我今天挑选的算法过于简单
为什么要哈希
因为字符串有时候会很长，如果出现什么特别长的字符串比如说qwqwqwqwq...（在此省略一万字）...qwqwqwq，如果只是为了查找它有没有出现过，为了它开一个十分大的字符串数组不仅浪费查找的时间还浪费空间。so哈希为此而生。
哈希是干嘛的
简而言之，哈希函数是一个压缩函数，通过将一个大的数字通过模一个质数压缩成一个小的数字，来达到能在数组里开的下的，并且可以用long long而不用自己写高精度来检查是否相等的函数。
也就是说，原来的数据范围可能是$10^100$，但其实里面可能没什么东西，哈希了一次后，数据范围就降到了$10^10$或更少，这样我们就可以将它用long long甚至int把它储存起来。
但或许你会问，这样的压缩后的数又有什么用呢？
要注意到，虽然我们不能将一个哈希后的数恢复到原来的内容，但同一内容无论何时哈希，得到的结果都是一样的。这样，当我们判断这个数曾经有没有出现过时，我们可以用少的多的空间管理同样多的东西。
1. 数组开的下：一般来说，一个用来判断一个$10^100$以内一个数是否出现过的bool数组是开不下的，但一个用来判断$10^6$个哈希数有没有出现的bool数组一般都能开的下。
2. 压缩数据：如果要直接储存一个大数你要自己写相关的高精度，但如果仅用来看看有没有出现而且数据量又很少，你完全可以用哈希。
3. 方便比较：不仅是一串数字，一个字符串，甚至是一张图，你都可以用一定的手段（比如说把它变成一个X进制数然后哈希）把它变成更容易储存和比较的哈希数。
接下来就是一个用哈希解决问题的题目。
P3370 【模板】字符串哈希
这题是一道经典的模板题。在处理的时候，我们可以将每一个字符串化成一个N进制数（最后用十进制数表示）后哈希。在比较的时候，我们就可以将哈希值排序，若前后两个字符串哈希值不同，就说明是两个不同的字符串。（这样远比一个个比较字符串字符简单的多）
#include<bits/stdc++.h>
#define base 150
#define mod 2145786907
#define MAXN 20000
//base用于解决字符串进位时的进制问题
//mod是用于哈希的模数
//MAXN表示数据范围
using namespace std;
int ni[MAXN];
int n;
//用于判断哈希值是否出现的函数，事实上在发现可以用排序解决问题时他就没啥用了
inline bool query(int hashed){
for(int i=1;i<n;i++){
if(hashed == ni[i]){
return true;
}
}
return false;
}
//用于生成哈希的函数
inline int hash1(string hs){
int x=0;
for(int i=0;i<hs.size();i++){
x=(x*base+hs[i])%mod;
//这里是哈希的核心算法，将字符串转化为一个base进制的数
//注意边乘边模以防止字符串的哈希超过int的数据范围
}
return x;
}
int main(){
string s;int ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>s;
//printf("%d\n",i);
ni[i]=hash1(s);
}
sort(ni+1,ni+1+n);
for(int i=1;i<n;i++){
if(ni[i]!=ni[i+1]){
ans++;
}
}
printf("%d",ans+1);
return 0;
}
哈希带来的一些问题
首先，因为哈希数量有限（毕竟你的模数定在那里），所以如果真的碰上一大堆数据的时候哈希要谨慎
其次，即使数据数量可能没那么多，你也要考虑到生日悖论和卡常。
生日悖论，指如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级(30人)中，存在两人生日相同的可能性更高。对于60或者更多的人，这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论，从这个数学事实与一般直觉相抵触的意义上，它才称得上是一个悖论。大多数人会认为，23人中有2人生日相同的概率应该远远小于50%。
根据生日悖论，即使你的数据并不多，你的哈希也有可能出现重复的情况。用哈希时，重复在所难免。
解决方案1 拉链法
⽤链表或其他数据结构将同⼀hash值的若⼲元素串联，如果遇到某个hash值就去链表上遍历,
解决方案2 开放寻址法
若某元素插⼊的散列地址已有元素占⽤，则使⽤⼀定⽅法（比如说：加上一个质数）寻找下⼀个可⽤地址
解决方案3 多重哈希
没错，你可以哈希好几次，就是把哈希函数以不同的质数多写几遍，比较的时候多次比较都相同后再说它们是一样的！
解决方案4 随机的防卡常/HACK的哈希
有时候，像CF之类的比赛，可能会有人故意看你的质数来卡常。
没错，你准备一个哈希质数表，这样的话每次程序运行随机取一个！
