模拟哈希表

#include<iostream>
#include<cstring>using namespace std;
const int N=100010;
int h[N],e[N],ne[N];
int idx=0;void insert(int x)
{int t=(x%N+N)%N;//模拟链表插入e[idx]=x,ne[idx]=h[t],h[t]=idx++;
}bool find(int x)
{int t=(x%N+N)%N;t=h[t];while(t!=-1)if(e[t]==x)return true;elset=ne[t];return false;
}int main()
{int n;memset(h,-1,sizeof h);scanf("%d",&n);while(n--){char op[2];int x;scanf("%s%d",op,&x);if(op[0]=='I')insert(x);else{if(find(x))puts("Yes");elseputs("No");}}return 0;
}

该方法是对于每个哈希冲突的位置，用一个模拟链表来存储，然后每次查找都是从这个模拟链表的头部开始依次查找，直到找到或者到了链表尾部才停止。

模拟链表的方式是用e[i]表示i下标存放的实际的数，ne[i]表示i下标所指向的下一位的下标。

因此，对于下标i，j，实际上是e[i]->e[j]。即利用下标获得指向的数，也利用下标得知本位制存放的数。