模拟散列表

拉链法，这里采用jdk中HashMap的hash函数

import java.io.*;
class Main {
    static int N = 100003;
    static int[] h = new int[N], e = new int[N], ne = new int[N];
    static int idx;
    static int hash(int k) {
        int hash = k ^ (k >>> 16);// 整数的hashCode就是自身
        return hash & 31; // Java  HashMap中的hash函数,原本是table.length - 1,这里为了方便直接取31
        //return (k % N + N) % N;
    }
    static boolean find(int x) {
        int k = hash(x);
        for (int i = h[k]; i != -1; i = ne[i]) {
            if (e[i] == x) return true;
        }
        return false;
    }
    static void insert(int x) {
        int k = hash(x);

        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx++;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(cin.readLine());
        for (int i = 0; i < n; i++) h[i] = -1;
        while (n-- > 0) {
            String[] s = cin.readLine().split(" ");
            if (s[0].equals("I")) insert(Integer.parseInt(s[1]));
            else {
                if (find(Integer.parseInt(s[1]))) System.out.println("Yes");
                else System.out.println("No");
            }
        }
    }
}

开放寻址法

import java.io.*;
class Main {
    static int N = 200003;
    static int[] h = new int[N];
    static int INF = 0x3f3f3f3f;
    static int hash(int k) {
        //int hash = k ^ (k >>> 16);// 整数的hashCode就是自身
        //return hash & 31; // Java  HashMap中的hash函数,原本是table.length - 1,这里为了方便直接取31
        return (k % N + N) % N;
    }
    static int find(int x) {// 返回的不仅仅是当前查找的位置，也能返回可以插入的位置
        int k = hash(x);
        while (h[k] != INF && h[k] != x) {
            k++;
            if (k == N) k = 0;
        }
        return k; 
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(cin.readLine());
        for (int i = 0; i < N; i++) h[i] = INF;
        while (n-- > 0) {
            String[] s = cin.readLine().split(" ");
            int k = find(Integer.parseInt(s[1]));
            if (s[0].equals("I")) h[k] = Integer.parseInt(s[1]);
            else {
                if (h[k] != INF) System.out.println("Yes");
                else System.out.println("No");
            }
        }
    }
}