哈希表模板

#哈希表模板| 来源: 网络整理| 查看: 265

哈希表

把大的区间映射到小的区间，一般为0~N x∈(-109,109) x mod 105∈（0，105) 模数一般要取成质数，且该质数要离2的整数次幂尽可能远，这样冲突的概率是最小的。可能出现冲突，按冲突的处理方式可分为两种

存储结构

在这里插入图片描述 1.开放寻址法只开一个数组，数组大小为2~3倍数据个数

#include #include using namespace std; const int N=200003;//为大于2~3倍数字个数的质数 int h[N];//只开一个数组，找不到的话换下一个坑位 int null=0x3f3f3f3f;//选择一个不在数值范围内的数作为空 int find(int x){//如果x存在，则返回x的位置，如果x不存在，则返回可插入x的位置 int k=(x%N+N)%N; while(h[k]!=null&&h[k]!=x){ k++; if(k==N)k=0;//如果找到尾，则从头开始 } return k; } int main(){ int n; scanf("%d",&n); memset(h,0x3f,sizeof(h)); for(int i=0;i h[pos]=x; }else{ if(h[pos]!=null)puts("Yes"); else puts("No"); } } return 0; }

2.拉链法

类似于邻接表

#include #include using namespace std; const int N=100003;//n为大于范围的第一个质数 int h[N];//存放链表头结点，没有则为-1; e[N],ne[N]; int idx=0; void insert(int x){//头插法 int k=(x%N+N)%N; e[idx]=x; ne[idx]=h[k]; h[k]=idx++; } bool query(int x){ int k=(x%N+N)%N; //这里注意不等于(x+N)%N //数学里-10%3=2， c++里 -10%3=-1 //为了让(x+N)%N不为负数， for(int i=h[k];i!=-1;i=ne[i]){ if(e[i]==x)return true; } return false; } int main(){ int n; scanf("%d",&n); memset(h,-1,sizeof(h)); //初始时哈希表为空 for(int i=0;i insert(x); }else{ bool ans=query(x); if(ans)puts("Yes"); else puts("No"); } } return 0; }

常用操作： 1.添加 2.查找 3.删除一般不会真的删除，只会开一个bool数组标记

字符串哈希方式

字符串前缀哈希法 1.定义某一前缀的哈希值：定义方法：把字符串看成是一个p进制的数，每一位字母表示p进制数的每一位数字，把字符串转化为数字在这里插入图片描述

注意：不能把字母映射为0，会把不同字符串映射成同样数字，是不对的假定人品足够好，不存在冲突，完全不考虑冲突的情况一般P取131或13331，Q取264 在这里插入图片描述用unsighed long long 存储会溢出就不用模226

2.对于某一字符串，先预处理出所有前缀的哈希

在这里插入图片描述

#include using namespace std; const int N=100010; typedef unsigned long long ULL; char str[N]; ULL p[N],h[N]; int P=131; ULL get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; } int main(){ int n,m; scanf("%d%d%s",&n,&m,str+1); p[0]=1; for(int i=1;i int l1,r1,l2,r2; scanf("%d%d%d%d",&l1,&r1,&l2,&r2); if(get(l1,r1)==get(l2,r2))puts("Yes"); else puts("No"); } return 0; }

相对KMP来讲除了不能求循环结，其他都可

【本文地址】

哈希表模板

哈希表模板

今日新闻

推荐新闻