维护一个集合，支持如下几种操作：

“I x”，插入一个数x；
“Q x”，询问数x是否在集合中出现过；
现在要进行N次操作，对于每个询问操作输出对应的结果。

输入格式
第一行包含整数N，表示操作数量。

接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。

输出格式
对于每个询问指令“Q x”，输出一个询问结果，如果x在集合中出现过，则输出“Yes”，否则输出“No”。

每个结果占一行。

数据范围
1≤N≤105
−109≤x≤109
输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

算法1：拉链法

思路

1.将x映射成小数组下标k，如果不同的x所得k相同，则以链表的形式存储

需要维护的变量：
N:操作数量 , a[N]:拉链数组 , e[N]:地址为N的数值 , ne[N]:地址为N的下一个节点地址，idx:节点地址

Java 代码

import java.util.*;

public class Main{
    private static int N = 100003;
    private static int[] a = new int[N];
    private static int[] e = new int[N];
    private static int[] ne = new int[N];
    //设0为空，地址从1开始
    private static int idx = 1;
    public static boolean find(int x){
        int k = (x % N + N) % N;
        //这里需要指针t来遍历，不能直接移动a[k]
        int t = a[k];
        while(t != 0){
            if(x == e[t]){
                return true;
            }
            t = ne[t];
        }
        return false;
    }
    public static void insert(int x){
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = a[k];
        a[k] = idx++;
    }
    public static void main(String[] args){

        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        while(m-- > 0){
           String opt = scanner.next();
           int x = scanner.nextInt();
           if("I".equals(opt)){
              insert(x);
           }else{
               System.out.println(find(x) == false ? "No" : "Yes");
           }
        }
    }
}

算法2：开放寻址法

思路

1.将x映射成小数组下标k，如果不同x所得k相同，则存储到k+1位置，以此类推
需要维护的变量：N:操作数量的两倍 , a[N]：寻址数组

Java 代码

import java.util.*;

public class Main{
    private static int N = 200003;
    //因为要用null标识节点空，所以类型为Integer
    private static Integer[] a = new Integer[N];
    public static int find(int x){
        int k = (x % N + N) % N;
        //别忘了第二个已存在的条件
        while(a[k] != null && a[k] != x){
            k++;
            if(k == N){
                k = 0;
            }
        }
        return k;
    }

    public static void main(String[] args){
        //先将所有位置设为null，标识为空
        for(int i = 0;i < a.length;i++){
            a[i] = null;
        }        
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        while(m-- > 0){
           String opt = scanner.next();
           int x = scanner.nextInt();
           if("I".equals(opt)){
              a[find(x)] = x;
           }else{
               //这是比较的是a[find(x)]
               System.out.println(a[find(x)] == null ? "No" : "Yes");
           }
        }
    }
}