⬅ 返回
1、拉链法
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6+3;
int h[N];//hash数组
int v[N],ne[N];//v存储的是结点的值 ne存储的是下一个结点编号
int node=0;
-----------------------------------------------------
void insert(int x)
{
int idx = (x%N+N)%N;
for(int i=h[idx];i!=-1;i=ne[i])
{
if(v[i]==x)
return;
}
v[node] = x;
ne[node] = h[idx];
h[idx] = node;
node++;
}
----------------------------------------------------------
bool find_hash(int x)
{
int idx = (x%N+N)%N;
for(int i=h[idx];i!=-1;i=ne[i])
{
if(v[i]==x)
return 1;
}
return 0;
}
int main(){
int n;
cin>>n;
memset(h,-1,sizeof h);
while(n--)
{
char c;
int x;
cin>>c>>x;
if(c=='I')
{
insert(x);
}else{
if(find_hash(x))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
}
2、开放寻址法
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e5+3;
---------------------------------------------------------------------
const int Max_int = 0x3f3f3f3f;//最大值
---------------------------------------------------------------------
int h[N];//hash数组
void insert(int x)
{
---------------------------------------------------------------------
int idx = (x%N+N)%N;//先模再加N再求模得到在数组中的下标 -10%3=-1
---------------------------------------------------------------------
while(h[idx]!=Max_int && h[idx]!=x)
{
if(idx==N)//当idx到达数组边界时回到下标0的位置
idx=0;
idx++;
}
h[idx]=x;
}
bool find_hash(int x)
{
int idx = (x%N+N)%N;
while(h[idx]!=Max_int)
{
if(h[idx]==x)
return true;
idx++;
}
return false;
}
int main(){
int n;
cin>>n;
--------------------------------------------------------------------------------------------------
memset(h,0x3f,sizeof h);//memset初始化内存 对字节初始化
//memset(h,-1,sizeof(h));
----------------------------------------------------------------------------------------------------
while(n--)
{
char c;
int x;
cin>>c>>x;
if(c=='I')
{
insert(x);
}else{
if(find_hash(x))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
}
3、区别
3.1、初始化
//拉链法
memset(h,-1,sizeof h);
//因为用-1表示链表结束结点
//开放寻址法
memset(h,0x3f,sizeof h);
//用正无穷表示此处还没有被标记 因为值的范围−1e9≤ x ≤1e9
3.2、方法
//拉链法
void insert(int x)
{
int idx = (x%N+N)%N;
for(int i=h[idx];i!=-1;i=ne[i])//遍历链表
{
if(v[i]==x)
return;
}
//头插法创建链表
v[node] = x;
ne[node] = h[idx];
h[idx] = node;
node++;
}
//开放寻址法
void insert(int x)
{
int idx = (x%N+N)%N;
while(h[idx]!=Max_int && h[idx]!=x)//遍历hash表
{
if(idx==N)
idx=0;
idx++;
}
h[idx]=x;
}