hash

import java.util.*;
public class Main{
    static int N=100003;
    static int[] h=new int[N];static int[] e=new int[N];static int[] ne=new int[N];
    static int idx=0;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=Integer.parseInt(sc.nextLine());
        init();
        for(int i=0;i<n;i++){
            String[] s=null;
            if(sc.hasNext()){
                s=sc.nextLine().split(" ");
            }
            if(s[0].equals("I")){
                int x=Integer.parseInt(s[1]);
                int k=hash(x);
                insert(k,x);
            }else if(s[0].equals("Q")){
                int x=Integer.parseInt(s[1]);
                int k=hash(x);
                if(query(k,x)){
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }
        }
    }

    public static int hash(int x){
        int k=(x%N+N)%N;
        return k;
    }

    public static void init(){
        Arrays.fill(h,-1);
    }
    public static void insert(int k,int x){
        e[idx]=x;
        ne[idx]=h[k];
        h[k]=idx++;
    }
    public static boolean query(int k,int x){
        for(int i=h[k];i!=-1;i=ne[i]){
            if(e[i]==x){
                return true;
            }
        }
        return false;
    }
}

开放寻址法

import java.util.*;
public class Main{

    static int N=200003;
    static int[] h=new int[N];static int f=0x3f3f3f3f;

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=Integer.parseInt(sc.nextLine());
        Arrays.fill(h,f);
        for(int i=0;i<n;i++){
            String[] s=null;
            if(sc.hasNext()){
                s=sc.nextLine().split(" ");
            }
            int x=Integer.parseInt(s[1]);
            int k=find(x);
            if(s[0].equals("I")){
                h[k]=x;
            }else if(s[0].equals("Q")){
                if(h[k]!=f){
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }
        }
    }

    public static int find(int x){
        int k=(x%N+N)%N;
        while(h[k]!=f&&h[k]!=x){//如果有这个数，返回这个数的位置 如果没有这个数 返回应该插入的位置
            k++;
            if(k==N){
                k=0;
            }
        }
        return k;
    }

}

字符串hash

import java.io.*;

public class Main{

    static int N=1000010;
    static long[] f=new long[N];//将字符串的前缀hash进行预处理
    static long[] p=new long[N];//p的幂次

    public static void main(String[] args)throws IOException{
        BufferedReader cin=new BufferedReader(new InputStreamReader(System.in));
        String[] str=cin.readLine().split(" ");
        int n=Integer.parseInt(str[0]);int m=Integer.parseInt(str[1]);
        String s=cin.readLine();
        s="0"+s;
        init(n,s);
        for(int i=0;i<m;i++){
            String[] ss=cin.readLine().split(" ");
            int l1=Integer.parseInt(ss[0]);int r1=Integer.parseInt(ss[1]);
            int l2=Integer.parseInt(ss[2]);int r2=Integer.parseInt(ss[3]);
            if(query(l1,r1,l2,r2)){
                System.out.println("Yes");
            }else{
                System.out.println("No");   
            }
        }
    }

    public static boolean query(int l1,int r1,int l2,int r2){
        if(f[r1]-f[l1-1]*p[r1-l1+1]==f[r2]-f[l2-1]*p[r2-l2+1]){
            return true;
        }else{
            return false;
        }
    }

    public static void init(int n,String s){
        p[0]=1;
        for(int i=1;i<=n;i++){
            f[i]=f[i-1]*131+(s.charAt(i)-'a'+1);
            p[i]=p[i-1]*131;
        }
    }

}