哈希表 - “为赋新词强说愁”
2026-07-20 15:46:18
发布于：浙江
自主学习笔记类产物。
——————————————————————————————————————————
map与哈希表（初学）
底层实现
map：红黑树
unorderd map：哈希表
哈希也称散列函数，它是一个不可逆的单项映射。
键值对：每一个键值key对应了一个取值value
哈希函数是一个带有模数的函数
很重要，它必须是质数。（不然发生哈希冲突的概率会很大）
越大，越不容易发生哈希冲突
可以使用两个哈希来避免哈希冲突。
公共溢出区：unsigned long long
string 哈希：进制不要太大，模数一定要大
可以使用unsigned long long
哈希能够表示任意一个子串的哈希值，所以它的应用范围相当广。
它还能维护变换的字符串。（带修改）
树哈希
判断两棵树是否是同构。
——————————————————————————————————————————
map（再学）
哈希的核心思想：把一个大块数据（字符串、数组）映射成一个数字，这个数字可以比较方便地用来比较，查找，去重。
字符串哈希：把字符串看作是一个B进制数字，并取模一个大质数M
哈希的常用技巧：
1.预处理前缀哈希（可以O(1)得到任何子串的哈希数值）
2.双哈希：用两个模数计算得到不同的哈希值，配对使用
哈希板子：https://www.luogu.com.cn/problem/P4305
这道题比较玄。会卡输入输出，所以记得关闭同步流。
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int a[N];
unordered_map<int,int>mp;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
mp.clear();
for(int i=1;i<=n;i++){
cin>>a[i];
if(mp.find(a[i])==mp.end()){
mp[a[i]]=1;
cout<<a[i]<<" ";
}
}
cout<<'\n';
}
return 0;
}
然后我们来看这个：https://www.luogu.com.cn/problem/P4503
给出N个字符串。相似的定义为：两个字符串只有一位不同。询问有多少对相似字符串。
核心思路是：枚举哪一位不同，然后挖掉这一位去比较剩下的部分。
我们预处理所有字符串前后缀，然后枚举j。最后计算挖掉j之后的结果。
#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;
typedef unsigned long long ull;//ull自然溢出，不需要取模
ull pre[N][205],hre[N][205],cnt[N],sum1;
//我在这里出现了错误，将205放到了前面（我以为205是字符个数没想到它是长度）
void init(string a){
//实际上是讲string看作进制
for(int i=0;i<a.size();i++)pre[sum1][i]=pre[sum1][i-1]*131+a[i];
//直接加a[i]（char类型）而不是用函数转化成数字，更加简洁
for(int i=a.size()-1;i>=0;i--)hre[sum1][i]=hre[sum1][i+1]*137+a[i];
//131和137双质数，相当于双哈希但是省去很多map什么的操作
}
int main(){
int n,l,s;
cin>>n>>l>>s;
for(int i=1;i<=n;i++){
string a;
cin>>a;
sum1++;
init(a);
}
ull ans=0;
for(int i=0;i<l;i++){
for(int j=1;j<=n;j++)cnt[j]=pre[j][i-1]*223+hre[j][i+1]*283;
//前233后283合并权重，给每个单独赋键值，在原先的基础之上再降低哈希冲突的概率
sort(cnt+1,cnt+1+n);
int sum=1;
for(int j=1;j<=n;j++){
if(cnt[j]==cnt[j-1])sum++;
else{
ans+=(sum*(sum-1))/2;//实际上是C(n,2)的简化版本
sum=1;
}
}
ans+=(sum*(sum-1))/2;
}
cout<<ans;
return 0;
}
这里空空如也
有帮助，赞一个