【算法】Hash存储——开放寻址法

模拟散列表

维护一个集合，支持如下几种操作：

I x，插入一个整数 x；
Q x，询问整数 x是否在集合中出现过；
现在要进行 N次操作，对于每个询问操作输出对应的结果。

输入格式
第一行包含整数 N，表示操作数量。

接下来 N行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

存储过程

存储方式：
// 防止出现复数情况
id = (x%N+N)%N
若q[id]!=null & q[id]!=x
id ++
若 id == N
id = 0

代码实现

#include #include using namespace std;const int N= 3e5 + 3;const int null =0x3f3f3f3f;int q[N];int Insert(int x){int u =(x%N + N)%N;while(q[u]!=null && q[u]!=x){u++;if(u==N){u=0;}}return u;}int main(){int n;cin>>n;memset(q, 0x3f3f3f3f, sizeof q);string op;int x;while(n--){cin>>op>>x;if(op[0]=='I'){q[Insert(x)] = x;}else{if(q[Insert(x)]!=null){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}}}