哈希表处理冲突的方式主要有两种一种是拉链法，另一种是开放寻址法
拉链法即开多个链表当发生冲突时把元素插入链表中
#include <iostream> #include <cstring> 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"<<endl; else cout<<"Yes"<<endl; } } return 0; }
