C++ 代码 拉链法模拟散列表

#include <iostream> 
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 3;//N为大于1e5的质数
int ne[N];  //存储节点指向的下一个位置
int e[N];   //存储节点值
int h[N];   //槽，即数组每个位置对应的单链表的第一个位置
int idx;    //标号，其中标号是所有单链表共用的，如idx=1可能是第一条单链表里的，而idx=2可能是最后一条单链表里的
void insert(int x)
{
    int k = (x % N + N) % N;    //hash函数,这样取防止有负数，得到的结果一定为0~N的正数
    e[idx] = x; //和链表一样，先存值
    ne[idx] = h[k]; //类似于插到头结点，即插到链表的第一个位置
    h[k] = idx++;   //更新头结点
}
int find(int x)
{
    int k = (x % N + N) % N;
    for(int i = h[k]; i != -1; i = ne[i]){  //从h[k]开始寻找，按链表向下寻找，直到遇到-1
        if(e[i] == x)
            return true;
    }
    return false;
}
int main()
{
    int n;
    int x;
    memset(h,-1,sizeof(h)); //开始时数组槽由于没有链表，全部初始化成-1
    string op;
    scanf("%d",&n);
    while(n--){
        cin >> op;
        scanf("%d",&x);
        if(op == "I")
            insert(x);
        else {
            if(find(x))
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}