3.13 模拟散列表 + 字符串哈希
创始人
2024-06-02 23:49:46
0次

哈希表

题目链接

存储方式

1. 拉链法

在这里插入图片描述
当出现地址冲突时，在数组下面开一个链。

单链表的模拟再复习一下，莫忘了
此外，对于数组大小N的选择，尽量选择质数，研究表明质数使得地址冲突产生的次数变少

int k=((x%N)+N)%N;这里注意，是防止x为负数


#include
#includeusing namespace std;const int N=1e5+3;int h[N],e[N],ne[N],idx=0; 
int n;void insert(int x){//将x插入哈希表int k=((x%N)+N)%N;++idx;e[idx]=x;ne[idx]=h[k];h[k]=idx;
}bool query(int x){int k=((x%N)+N)%N;for(int i=h[k];i!=-1;i=ne[i]){if(e[i]==x)return true;}return false;
}int main(){memset(h,-1,sizeof h);cin>>n;while(n--){string s;int x;cin>>s;if(s=="I"){cin>>x;insert(x);}else{cin>>x;if(query(x))cout<<"Yes"<
2. 开放寻址法

思路：

  1. 插入： 映射到k，发现如果被占了，那就从后看找到空的再插入
  2. 查找： 映射到k，一直往后找直到等于null。如果能找到就有，不能找到就没
    使用find实现，find用于查找x所在的下标或者是要被插入的下标

#include
#includeusing namespace std;const int N=1e5+3,null=0x3f3f3f3f;int h[N]; 
int n;int find(int x){//对于x，找一下其在什么位置可以放置，如果没有返回0 int k=((x%N)+N)%N;while(h[k]!=null&&h[k]!=x){k++;if(k==N)	k=0;}return k;
}  int main(){memset(h,0x3f3f3f3f,sizeof h);cin>>n;while(n--){string s;int x;cin>>s;if(s=="I"){cin>>x;int k=find(x);h[k]=x;}else{cin>>x;if(h[find(x)]!=null)cout<<"Yes"<

字符串哈希

题目链接

思路

因为题目是判断区间内字符串是否相等，那么考虑类似的前缀和
定义
“abcdefg”
h[1]=“a”
h[2]=“ab”
h[3]=“abc”
对于每一个h[]，我们都将其看作一个p进制数，
其中abc=(123)p
这样每个数都会对应一个值
在字符串哈希中，比较特殊的是，如果我们取P=131，那么发生地址冲突的概率仅为0.01%
因此这里我们就不考虑地址冲突
那么如果要求[L,R]区间内的字符串哈希值
那么就是：
在这里插入图片描述
然后其实我们都不用存，因为假设了哈希地址不冲突，直接每次求值即可。


#include
#includeusing namespace std;
const int N=1e5+10;//h用于存数，p用于存p的几进制 
int h[N],p[N];
int P=131;int n,m;unsigned long long get(int l, int r){return h[r]-h[l-1]*p[r-l+1];
}int main(){cin>>n>>m;string s;cin>>s;p[0]=1;for(int i=1;i<=n;i++){h[i]=h[i-1]*P+s[i-1];p[i]=p[i-1]*P;}while(m--){int l1,l2,r1,r2;cin>>l1>>r1>>l2>>r2;if(get(l1,r1)==get(l2,r2))cout<<"Yes"<
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：SystemVerilog教程第一章：什么是测试激励文件

下一篇：java ArrayList源码分析（深度讲解）

相关内容

热门资讯

麦芒是安卓系统吗,深度解析安卓... 你有没有想过，手机里的那个麦芒，它是不是安卓系统呢？这个问题，估计不少手机控都好奇过吧！今天，就让我...
苹果x系统感觉像安卓,安卓风潮... 你有没有发现，最近苹果的X系统好像有点儿像安卓呢？是不是觉得苹果的“高贵”形象突然变得有点儿接地气了...
小米的安卓系统设置在哪,轻松生... 你有没有发现，小米手机的操作界面简洁又美观，功能强大到让人爱不释手？但是，有时候你可能会觉得，这个设...
安卓系统荣耀排第一,引领智能手... 你知道吗？在智能手机的世界里，有一个系统可是风头无两，那就是安卓系统！而在这众多安卓手机品牌中，有一...
充电宝带安卓系统,便携式智能电... 你有没有想过，你的充电宝也能拥有自己的操作系统呢？没错，就是安卓系统！听起来是不是很酷？想象你的充电...
安卓类原生系统手机推荐,精选原... 你有没有想过，拥有一部安卓类原生系统手机，就像是拥有了掌控自己世界的魔法棒？没错，原生系统带来的流畅...
努比亚安卓13系统下载,下载与... 你有没有听说？努比亚手机最近可是大动作连连呢！他们推出了全新的安卓13系统，而且现在就可以下载啦！是...
一加5系统安卓10,安卓10系... 你有没有注意到，你的手机最近是不是变得特别聪明了？没错，我要说的就是那款让人眼前一亮的一加5手机，它...
ios系统数据转到安卓,iOS... 你是不是也有过这样的经历？手里拿着一台运行着iOS系统的苹果手机，突然有一天，你发现安卓手机的世界也...
安卓系统用什么修图,基于安卓系... 手机里的照片总是不够完美？别急，今天就来给你揭秘，安卓系统上那些超好用的修图神器！无论是磨皮美颜，还...
安卓使用低系统的软件 你有没有发现，手机里的那些老古董安卓系统，竟然还能玩出新花样？没错，就是那些使用低系统版本的安卓手机...
安卓系统怎么开通漫游,安卓系统... 你有没有遇到过这种情况：出国旅行，满心欢喜地想要用手机拍下那些美丽的风景，结果却发现信号全无，只能干...
编曲用软件推荐安卓系统,打造个... 音乐爱好者们，是不是在为编曲软件发愁呢？别急，今天就来给你推荐几款适合安卓系统的编曲神器，让你的音乐...
安卓系统版本更新后黑屏,安卓系... 最近是不是你也遇到了安卓系统更新后黑屏的尴尬情况？这可真是让人头疼啊！手机屏幕突然变成了一片漆黑，啥...
国家企业公示系统安卓app 你有没有发现，现在的生活越来越离不开手机了？无论是工作还是生活，手机都能帮我们解决不少麻烦。今天，我...
安卓系统更新提示失败,揭秘原因... 最近你的安卓手机是不是也遇到了更新提示失败的小麻烦？别急，让我来给你详细说说这个让人头疼的问题，让你...
ops电脑装安卓系统,开启多系... 你有没有想过，你的电脑装上安卓系统会是怎样的场景呢？想象你那台曾经只用来处理文档和浏览网页的电脑，突...
安卓系统触屏校准在哪,轻松实现... 手机屏幕总是感觉有点歪？别急，今天就来教你怎么给安卓系统的手机进行触屏校准，让你的操作更加精准哦！一...
安卓系统id6,揭秘新一代操作... 你有没有发现，最近你的安卓手机突然变得有点不一样了？是不是觉得系统运行得更加流畅，界面也焕然一新？别...
安卓系统用的华为应用,探索智能... 你知道吗？在安卓系统里，华为的应用可是个宝库呢！它们不仅功能强大，而且使用起来超级方便。今天，就让我...