哈希表问题
作用:把一个比较庞大的值域映射到一个比较小的数据范围内。
哈希表存储结构
开放寻址法:分为线性探测,二次探测,双重散列。
拉链法:在已被占用的位置链接一个元素。
题目描述
模拟散列表 840.题目自己看看奥
思路
搞懂这道题需要对模拟单链表复习一下,不然看不懂最关键的一步模板,因为y总用的拉链法。
e [idx]= x ; ne [idx]=h[k];h[k]=idx++;
首先明白e是存放真实数值的数组,h只存放数组所在的下标,用图像模拟更好理解。
查找就很直白,先找到k所在的地方然后遍历这条链,利用next数组找下标,通过对比e数组内的值看看有没有相同的元素。
算法1 拉链法
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100003;
int h[N],e[N],ne[N],idx;
void insert(int x)
{
int k=(x%N+N)%N;
e[idx]=x;//把x先存在e数组里面
ne[idx]=h[k];//k处的顶端指向next数组
h[k]=idx++;//
}
bool find(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()
{
int n;
scanf("%d",&n);
memset(h,-1,sizeof h);//将某一块内存中的内容设定为指定的值
while(n--)
{
char op[2];
int x;
scanf("%s%d",op,&x);
if(op[0]=='I') insert(x);
else
{
if(find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
算法2 开放定址法
C++代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 200003,null = 0x3f3f3f3f;//因为null不在-10e9到10e9内
int h[N];
void insert(int x)
{
}
int find(int 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);//将某一块内存中的内容设定为指定的值
while(n--)
{
char op[2];
int x;
scanf("%s%d",op,&x);
int k=find(x);
if(op[0]=='I') h[k]=x;
else
{
if(h[k]!=null) puts("Yes");
else puts("No");
}
}
return 0;
}