当前位置：科技动态 > Hash* table

Hash* table

发布：2023-09-30 01:46

一共引入了四三种方法开放寻址法 Zipper 法 Trie 字典树法前两种方法是本题算法要求掌握的。 Trie字典树方法将数字转换为二进制进行运算 #包括使用命名空间 std；常量 int N=1e5+10; int son[32*N][2],idx,cnt[N]; void insert(int x){int p=0,u;for(int i=32;i>=0;i--){u=x>>i&1;if(!son[p][u])son [p][u]=++idx;p=son[p][u];}} int find(int x){int p=0,u;for(int i=32;i>=0;i--){u=x>>i&1;if(!son[p][u])return 0;p=son[p][u];}返回1; } int main(){int n;cin>>n;while(n--){char op[2];int x;x=x+1e9;cin>>op>>x;if(*op==' I') {insert(x);//cout<<"haha"< #包括使用命名空间 std； const int N=2000003,null=0x3f3f3f3f; 整数 h[N]; int find(int x){int k=(x%N+N)%N;while(h[k]!=null&&h[k]!=x){//如果没有坑了，继续找下一个坑位置，所以不能使用 ifk++;if(k==N)k=0;}return k; } int main(){memset(h,0x3f,sizeof h);int n;scanf("%d", &n);while(n--){char op[2];int x;scanf("%s% d", op, &x);if(*op=='I')h[find(x)]=x;else {if(h[find(x)]==null)puts("否");否则 put("是");}}返回 0; } 拉链法来源 #包括#include using 命名空间 std;const int N = 1e5 + 3; // 取第一个大于1e5的素数，取素数冲突概率最小的。你可以百度 //* 开一个槽 h int h[N], e[N], ne[N], idx; //邻接表 void insert(int x) {//在c++中，如果是负数，它的模也是负数，所以先加N，再%N。必须是正数 int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];//头节点取模得到的数存储的数字都是头节点后面的小尾 h[k] = idx++; }bool find(int x) {//使用与上面相同的哈希函数将x映射到0-1e5之间的数字 int k = (x % N + N) % N; for (int i = h[k] ; i != -1; i = ne[i]) {if (e[i] == x) {返回 true;}}返回 false; }int n;int main() {cin >> n;memset(h, -1, sizeof h); //先清空槽位。空指针一般用-1表示 while (n--) {string op;int x;cin >> op >> x;if (op == "I") {insert(x);} else {if ( find(x)) {puts("是");} else {puts("否");}}}返回 0; } #包括 #包括使用命名空间 std；常量 int N=1e5+10,M=1e5; int h[N],e[N],ne[N],idx=1; void insert(int x){int k=x%M;e[idx]=x;ne[idx]=h[k];h[k]=idx++; } int find(int x){int k=x%M;for(int i=h[k];i!=0;i=ne[i]){if(e[i]==x)return 1; }返回0； }int main(){int n;scanf("%d", &n);while(n--){char op[2];int x;scanf("%s%d", op, &x);x+= 1e9;if(*op=='I')insert(x);else {if(find(x))puts("是");else puts("否");}}返回 0; }