哈希表处理冲突的方式主要有两种一种是拉链法,另一种是开放寻址法
拉链法即开多个链表当发生冲突时把元素插入链表中
#include
#include using namespace std; const int N =1e5+3; int h[N],e[N],ne[N],idx,n; void insert(int x) { int k = (x % N + N) % N; e[idx] = x; ne[idx] = h[k]; 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() { cin>>n; memset(h, -1 ,sizeof h); while(n--) { int x; string op; cin>>op>>x; if(op == "I") insert(x); else { if(find(x)) puts("Yes"); else puts("No"); } } return 0; }
开放寻址法
#include"bits/stdc++.h"
using namespace std;
const int N=200003,null=0x3f3f3f3f;
int h[N];
int find(int x)
{
int t=(x%N+N)%N;
while(h[t]!=null&&h[t]!=x)
{
t++;
if(t==N) t=0;
}
return t;
}
int main()
{
memset(h, 0x3f, sizeof h);
int n;
cin>>n;
while(n--)
{
string ch;int x;
cin>>ch>>x;
if(ch=="I") h[find(x)]=x;
else
{
if(h[find(x)]==null) cout<<"No"<
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)