说实话今天上课是真的没有上明白，直到后来疯狂找资料才感觉学得有点明白了（bushi
哈希表
哈希表是一种实现高校查找的数据结构，也叫散列，哈希能实现把任意长度的输入，通过散列算法，变换成固定长度的输出，这个输出值就是散列值。
hash的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围
hash逆天之o(1)复杂度——通过hash可以直接计算出元素的存储地址，是一种“空间换时间”的做法，（空间相对来说较为廉价）能够大大提高查找效率
从某个角度看，hash可以是一种加密方法，通过对数字或字符串进行加密，来比较与查询对应数字或字符串的hash值
构造hash：
1、整数的Hash函数构造方法
（1）直接取余法
关键字k除以m，取余数作为在Hash表中的位置。函数表达式可以写成：h(k)=k mod m （注：一般m选择为素数）
代码：
ll p=abs(x%md);
while(b[p]!=1808504320951916825)
{
if(b[p]==x)
return true;
else
p++;
}
b[p]=x;
return false; （2）乘积取整法
关键字k乘以一个在(0,1)中的实数（最好是无理数），得到一个(0,1)之间的实数；取出其小数部分，乘以m，再取整数部分，即得K在Hash表中的位置。
函数表达式可以写成：
2、字符串hash
对于字符串hash，我们可以将其转换成一个base进制的数，然后存入数组中，常用的质数有：131、233、19260817
代码：
#define ull unsigned long long
ull base=131;
ull hashs(string x)
{
int len=x.length();
ull ans=0;
for(int i=0;i<len;i++)
ans=(ans*base+x[i])%mod;
return ans;
}3、排列的hash函数构造——康托展开
康托展开是一个全排列到一个自然数的双射，实质是计算当前排列在所有由从小到大全排列中的顺序，是可逆的
假设12345是第一个序列，以52413为例，该序列展开后为：
由于康托展开从0开始计数，所以52413的编号为107
逆展开：
107-1=106
106/4!=4.........10 有4个比它小的——5
10/3!=1.............4 有1个比它小的——2
4/2!=2...............0 有2个比它小的——4
0/1!=0...............0 有0个比它小的——1
0/0!=0...............0 有0个比它小的——3
所以第107个序列是52413
下面是一些题目：
P4305 [JLOI2011] 不重复数字
这是关于整数的哈希，把数据存到一个很大很大的数组里，然后开始查找
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e7+5;
int md=1e6+5;
ll t;
ll n;
ll k;
ll b[N];
inline bool find(ll x)
{
ll p=abs(x%md);
while(b[p]!=1808504320951916825)
{
if(b[p]==x)
return true;
else
p++;
}
b[p]=x;
return false;
}
inline ll read()
{
ll x=0,f=0;
char c=getchar();
while (!isdigit(c))
f|=c=='-',c=getchar();
while (isdigit(c))
x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?-x:x;
}
int main()
{
t=read();
while(t--)
{
memset(b,25,sizeof(b));
n=read();
for(ll i=1;i<=n;i++)
{
k=read();
if(!find(k))
cout<<k<<" ";
}
cout<<endl;
}
}P3370 【模板】字符串哈希
这里提供三个魔板
1、自动溢出（还是比较喜欢这个）
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=1e5+5;
ull base=233;
ull a[N];
int n;
string w;
int ans=1;
ull hashs(string s)
{
int len=s.length();
ull ans=0;
for(int i=0;i<len;i++)
ans=ans*base+s[i];
return ans&0x7fffffff;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>w;
a[i]=hashs(w);
}
sort(a+1,a+1+n);
for(int i=2;i<=n;i++)
if(a[i]!=a[i-1])
ans++;
cout<<ans<<endl;
return 0;
}2、单hash
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define ull unsigned long long
ull base=131;
ull a[N];
string s;
int n,ans=1;
ull mod=212370440130137957ll;
ull hashs(string x)
{
int len=x.length();
ull ans=0;
for(int i=0;i<len;i++)
ans=(ans*base+x[i])%mod;
return ans;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s;
a[i]=hashs(s);
}
sort(a+1,a+1+n);
for(int i=2;i<=n;i++)
if(a[i]!=a[i-1])
ans++;
cout<<ans<<endl;
}3、双hash
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define ull unsigned long long
ull base=131;
struct data
{
ull x,y;
}a[N];
string s;
int n,ans=1;
ull mod1=19260817;
ull mod2=19260813;
ull hash1(string w)
{
int len=w.length();
ull ans=0;
for(int i=0;i<len;i++)
ans=(ans*base+s[i])%mod1;
return ans;
}
ull hash2(string w)
{
int len=w.length();
ull ans=0;
for(int i=0;i<len;i++)
ans=(ans*base+s[i])%mod2;
return ans;
}
bool cmp(data a,data b)
{
return a.x<b.x;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s;
a[i].x=hash1(s);
a[i].y=hash2(s);
}
sort(a+1,a+1+n,cmp);
for(int i=2;i<=n;i++)
if(a[i].x!=a[i-1].x||a[i].y!=a[i-1].y)
ans++;
cout<<ans<<endl;
return 0;
}P3879 [TJOI2010] 阅读理解
思路很简单：把每一个单词存入哈希函数，查找生词时直接就可以找对应哈希值是否有出现过即可
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
#define ull unsigned long long
ull n;
struct paper
{
ull num;
string word[N];
}ess[N];
ull ha[N][N];
ull base=311;
ull m;
ull ans;
bool exist[N];
string oo;
ull hashs(string s)
{
ans=0;
ull len=s.length();
if(len==1)
return s[0];
for(ull i=0;i<len;i++)
ans=ans*base+s[i];
return ans&0x7fffffff;
}
int main()
{
cin>>n;
for(ull i=1;i<=n;i++)
{
cin>>ess[i].num;
for(ull j=1;j<=ess[i].num;j++)
{
cin>>ess[i].word[j];
ha[i][j]=hashs(ess[i].word[j]);
}//ha[i][j]代表第i篇文章的第j个单词的哈希值
}
cin>>m;
while(m--)
{
memset(exist,0,sizeof(exist));
cin>>oo;
ull k=hashs(oo);
for(ull i=1;i<=n;i++)
for(ull j=1;j<=ess[i].num;j++)
{
if(k==ha[i][j])
{
exist[i]=true;
break;
}
}
for(ull i=1;i<=n;i++)
if(exist[i])
cout<<i<<" ";
cout<<endl;
}
}P1481 魔族密码
对每一个字符串进行哈希运算并保存起来，然后开两个循环依次进行遍历，找长字符串中是否有短字符串的哈希值，ha[i][j]存的是第i个字符串从开始到第j位的子串的哈希值，
代码：
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=3005;
ull base=131;
ull md=212370440130137957ll;
ull f[N];
ull ha[N][N];
ull maxx;
ull n;
string s[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>s[i];
for(int i=1;i<=n;i++)
{
ull len=s[i].length();
ha[i][0]=s[i][0];
for(int j=0;j<=len-1;j++)
ha[i][j]=ha[i][j-1]*base+s[i][j];
}
for(int i=1;i<=n;i++)
{
ull ans=0;
ull len1=s[i].length()-1;
for(int j=1;j<=n;j++)
{
ull len2=s[j].length()-1;
if(len1>=len2&&ha[i][len2]==ha[j][len2])
f[i]++;
}
}
for(int i=1;i<=n;i++)
maxx=max(maxx,f[i]);
cout<<maxx<<endl;
return 0;
}P4503 [CTSC2014] 企鹅 QQ
这道蓝题思路很有意思
题意就是：在所有字符串中每删除一个同位字符，就将剩余的字符按照原来的顺序拼接起来并比较，最后累加
思路：先做预处理，将每个字符串在去掉了第i个字符后的字符串的哈希值通过进制来存储起来（第i个字符前面的字符串以及第i个字符后面的的字符串），然后对其之和用新数组hashs储存，并且按位实时更新，对其进行排序，然后对其进行遍历，若有前后相同的值则累加
代码：
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=3e4+5;
const int M=205;
ull n,l,shu;
char s[M];
ull base1=133,base2=233;
ull k1=131,k2=233;
ull hash1[N][M];
ull hash2[N][M];
ull hashs[N];
int main()
{
cin>>n>>l>>shu;
for(ull i=1;i<=n;i++)
{
scanf("%s",s+1);
for(ull j=1;j<=l;j++)
hash1[i][j]=hash1[i][j-1]*base1+s[j];
//求去掉i字符前面的字符串的哈希值
for(ull j=l;j>=1;j--)
hash2[i][j]=hash2[i][j+1]*base2+s[j];
//求去掉i字符后面的字符串的哈希值
}
ull ans=0,t=1;
for(ull j=1;j<=l;j++)
{
for(ull i=1;i<=n;i++)
hashs[i]=hash1[i][j-1]*k1+hash2[i][j+1]*k2;
//去掉i字符后新字符串的哈希值
sort(hashs,hashs+1+n);
for(ull i=2;i<=n;i++)
{
if(hashs[i]==hashs[i-1])
{
ans+=t;
t++;
}
else
t=1;
}
}
cout<<ans<<endl;
return 0;
}参考：哈希（hash）基础（学不会来找我）-CSDN博客文章来源：https://www.toymoban.com/news/detail-836810.html
字符串哈希 - OI Wiki (oi-wiki.org)文章来源地址https://www.toymoban.com/news/detail-836810.html
到了这里，关于DAY_8（哈希hash）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
