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源码分析（深度讲解）

相关内容

热门资讯

安卓系统对比骁龙,性能与生态的... 你有没有想过，为什么你的手机里装的是安卓系统，而不是苹果的iOS呢？又或者，为什么你的安卓手机里搭载...
qt程序安卓系统运行,基于Qt... 你有没有想过，为什么有些手机上的程序运行得那么顺畅，而有些却总是卡得让人抓狂？今天，就让我来给你揭秘...
安卓系统免费应用推荐,助你畅享... 手机里的应用是不是越来越多，有时候都挑花眼了呢？别急，今天我就来给你推荐一些安卓系统上的免费应用，让...
安卓系统视频通话app,打造无... 你有没有发现，现在手机上的视频通话功能越来越强大了？尤其是安卓系统上的那些视频通话app，简直让人爱...
安卓系统发现高危病毒,守护手机... 亲爱的手机用户们，最近可是有个大消息在安卓系统用户群里炸开了锅！没错，就是安卓系统发现了一款高危病毒...
安卓系统疯狂弹广告,揭秘广告软... 你有没有遇到过这种情况？手机里突然弹出一个广告，让你瞬间心情大崩溃？没错，说的就是安卓系统那让人头疼...
ebook 10进入安卓系统 你有没有发现，最近你的安卓手机里多了一个新伙伴——那就是电子书（ebook）10！没错，就是那个我们...
安卓系统如何调听筒,安卓系统调... 手机听筒声音突然变小了？别急，让我来教你如何轻松调教安卓系统的听筒，让它重新恢复活力！一、检查音量设...
安卓系统是怎么手机,解锁智能生... 你有没有想过，我们每天不离手的安卓手机，它背后的安卓系统究竟是怎么一回事呢？今天，就让我带你一探究竟...
安卓系统能代替windows系... 你有没有想过，我们日常使用的安卓系统和Windows系统，哪个才是真正的霸主呢？是不是有时候觉得安卓...
lp108安卓系统,功能特点与... 你有没有听说最近LP108安卓系统火得一塌糊涂？没错，就是那个让无数手机用户都为之疯狂的新系统！今天...
安卓系统挂载u盘,轻松实现数据... 你有没有想过，你的安卓手机或平板电脑突然变成了一个移动的U盘？没错，就是那种可以随意存取文件的神奇设...
i5 安卓系统,引领智能终端新... 你有没有想过，为什么你的手机总是卡得要命，而别人的手机却能流畅如丝？是不是因为你的手机搭载了那个传说...
安卓手机系统没有升级,揭秘潜在... 你有没有发现，你的安卓手机系统好像好久没升级了呢？是不是觉得有点out了？别急，今天就来给你详细聊聊...
安卓14系统定制v,创新功能与... 你知道吗？最近安卓系统又出新花样了！安卓14系统定制版V，这名字听起来就让人兴奋不已。今天，就让我带...
手机安卓系统越高越好,探索最新... 你有没有发现，每次手机更新系统，你的手机就像脱胎换骨了一样？没错，说的就是你，那个安卓手机！今天，咱...
鸿蒙系统怎么用回安卓,轻松实现... 你是不是也和我一样，对鸿蒙系统的新鲜感还没过，却又忍不住想回到熟悉的安卓世界？别急，今天就来手把手教...
苹果7跟安卓系统,性能对决与用... 你有没有想过，为什么苹果7那么受欢迎，而安卓系统却有着庞大的用户群体？今天，我们就来聊聊这个话题，看...
安卓手机刷简化系统,轻松实现流... 你有没有想过，你的安卓手机其实可以变得更加轻快、流畅呢？没错，就是通过刷简化系统！今天，就让我带你一...
社保掌上通安卓系统,轻松掌握在... 你有没有发现，现在的生活越来越离不开手机了？无论是购物、聊天还是办公，手机都能轻松搞定。这不，今天就...