西安网站制作定制,private messages for wordpress,百度开户代理公司,淘宝网站建设哪个类目1.hash是什么#xff1f;
定义#xff1a;hash,一般翻译做散列、杂凑#xff0c;或音译为哈希#xff0c;是把任意长度的输入#xff08;又叫做预映射pre-image#xff09;通过散列算法变换成固定长度的输出#xff0c; 该输出就是散列值。这种转换是一种压缩映射…1.hash是什么
定义hash,一般翻译做散列、杂凑或音译为哈希是把任意长度的输入又叫做预映射pre-image通过散列算法变换成固定长度的输出 该输出就是散列值。这种转换是一种压缩映射也就是散列值的空间通常远小于输入的空间。
这么一说肯定会觉得很难这百度百科果然不适合小白可恶
用大白话来说举个例子我们有一个字符串ABC我们会通过一系列运算将其转换为哈希值使其与别的字符串不相同
哈希算法不过是一个更为复杂的运算它的输入可以是字符串可以是数据可以是任何文件经过哈希运算后变成一个固定长度的输出 该输出就是哈希值。但是哈希算法有一个很大的特点就是你不能从结果推算出输入,所以又称为不可逆的算法
2.map容器mapT1, T2SUM
注T1和T2都是数据类型
map是STL的一个关联容器它提供一对一的hash。
T1可以称为关键字(key)每个关键字只能在map中出现一次
T2可以称为该关键字的值(value)
因此我们就可以借助map函数来轻易实现hash的用法那么我们来看几个简单的例题
3.例题
1第一题 字符串哈希模版 题解刚做这道题的时候我并没有了解到map函数导致我的代码显得很冗长是自己去实现map函数的功能的我首先想到的就是可不可以将abc这种字符串换成一个整数然后我就想着直接累加后续我又想到了可能会存在冲突比如说abc的值等于cba的值因此我给字符串加上了进制每一位都多乘一个10然后我才过的如果当前那个数组存在当前值就减一最后输出总值请看AC代码
#includebits/stdc.h
using namespace std;
int n,sum;
char a[10005][2000];
unsigned long long b[10005];
int len[10005];
unsigned long long tt47;
int main()
{scanf(%d,n);for(int i1;in;i){int cnt0;int ans0;scanf(%s,a[i]);len[i]strlen(a[i]);while(cntlen[i]){ansans*tt(unsigned long long)a[i][cnt];cnt;}b[i]ans;}sort(b1,bn1);for(int i1;in-1;i){if(b[i]!b[i1])sum;}printf(%d,sum1);return 0;
}
2 第二题错误点名的开始 、题解这时候我就已经学会用map函数了因此直接用map函数可以迅速秒杀这道题
#include bits/stdc.h
using namespace std;
int n,m;
string s;
mapstring,intsum;
int main()
{scanf(%d,n);for(int i1;in;i){cins;sum[s]1;}scanf(%d,m);for(int i1;im;i){cins;if(sum[s]1){printf(OK\n);sum[s];continue;}if(sum[s]1)printf(WRONG\n);if(sum[s]1)printf(REPEAT\n);}return 0;
} 第三题密文搜索 题解我们只需要将后面的密码转变为哈希数然后从上述字符串中取出连续的八个字符如果其哈希值和下面的密码一样的话就说明配对成功次数要加1最后统计总数即可
#includebits/stdc.h
using namespace std;
mapstring,intsum;
string s,t;
int n;
int ans;
int main()
{cins;scanf(%d,n);for(int i0;in;i){cint;sort(t.begin(),t.end());sum[t];}for(int i0;is.size()-7;i){ts.substr(i,8);sort(t.begin(),t.end());anssum[t];}printf(%d,ans);return 0;
}
