开散列方法(又名拉链法):

一般意义上的哈希表模型题:
维护一个集合，支持如下几种操作：
    1. I x，插入一个数 x;
    2. Q x，询问数 x 是否在集合中出现过;

注意要点:

一般情况下,把数组长度定义为N的2倍,
且长度最好为一个质数为最优策略,原因是:
    如果n取成偶数,那么x取奇数mod n为奇数,或x取偶数mod n为偶数
        则奇数永远不可能映射到偶数的槽位上,
        偶数也永远没办法映射到奇数的下标上,
        以及还有包括n的因子存在的情况下,
        都会导致选择变少了,那么随机的概率失去均衡,
        冲突的概率比较大,容易产生割裂,
        所以n一般取质数降低冲突概率,例如:数据量为10^5则可以开成200003

具体实现代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#define N 200003
using namespace std;

int n;
int h[N], e[N], ne[N], idx; //数组模拟邻接表

void add(int a,int b)   //添加一个结点a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool find(int x)    //查询
{
    int t = (x % N + N) % N;
    for (int i = h[t]; ~ i ;i = ne[i])
        if(e[i] == x)
            return true;
    return false;
}

void insert(int x)  //插入
{
    if(find(x)) return ;    //如果存在,直接返回

    //需要得到一个非负的余数
    //因为C++取模跟数学定义里面取模运算不一样
    //C++里面取模会得到负数,数学定义里面会得到正数,所以需要对代码进行非负处理
    int t = (x % N + N) % N;
    add(t, x);
}

int main()
{
    memset(h, -1,sizeof h);//对头表进行初始化
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if(*op == 'I')  insert(x);
        else
        {
            if(find(x)) puts("Yes");
            else    puts("No");
        }
    }
    return 0;
}