哈希表(模板题：AcWing.840)

方法1：拉链法

• 先求哈希值，然后在哈希值为下标的数组位置存储一条链表，然后往下依次插入数据
• 哈希表一般很少用删除操作，如果需要删除，我们写的代码也不是真正删除，而是在待删除的位置上打上标记，以表示该位置已经不可用
• 因为元素取值是$10^{-9}$~$10^9$，所以求哈希值的时候$(x)modN$可能为负数，所以应该$((x)mod N + N)modN$

Java代码

import java.io.*;
import java.util.*;
public class Main{
    private static int[] hash,e,ne;
    private static int idx = 0;
    private static final int N = 100003;

    static void insert(int x){
        //求哈希值,哈希值可能是负数，所以+N再modN
        int t = (x % N + N) % N;
        //头插法
        e[idx] = x;
        ne[idx] = hash[t];
        hash[t] = idx;
        idx++;
    }

    static boolean find(int x){
        int t = (x % N + N) % N;
        for(int i = hash[t]; i != -1; i = ne[i]){
            if(e[i] == x) return true;
        }
        return false;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        hash = new int[N];
        Arrays.fill(hash,-1);
        e = new int[N];
        ne = new int[N];
        while(n-- > 0){
            String[] s = br.readLine().split(" ");
            int x = Integer.parseInt(s[1]);
            if(s[0].equals("I")){
                insert(x);
            }else{
                if(find(x)) System.out.println("Yes");
                else System.out.println("No");
            }
        }
    }
}

方法2：开放定址法

• 求哈希值，如果哈希值所在的位置有元素，就往后挪一位，此时有两种情况：
  1.哈希表中本来就有这个元素，则找到这个元素所对应的数组下标
  2.哈希表中本来没有这个元素，则找到对应哈希值为下标，往后找的第一个空位置存放该元素
• 数组长度为数据总量的2到3倍，哈希冲突的概率能够降低

Java代码

import java.io.*;
import java.util.*;
public class Main{
    private static int[] hash;
    private static final int N = 200003;
    private static int blank = Integer.MAX_VALUE;

    static int find(int x){
        //寻找可以插入的位置
        int t = (x % N + N) % N;
        while(hash[t] != blank && hash[t] != x){
            t++;
            if(t == N) t = 0;
        }
        return t;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        hash = new int[N];
        Arrays.fill(hash,Integer.MAX_VALUE);
        while(n-- > 0){
            String[] s = br.readLine().split(" ");
            int x = Integer.parseInt(s[1]);
            int t = find(x);
            if(s[0].equals("I")){
                hash[t] = x;
            }else{
                if(hash[t] != blank) System.out.println("Yes");
                else System.out.println("No");
            }
        }
    }
}

字符串前缀哈希(模板题：AcWing.841)

• 字符串哈希可以解决一些kmp都难以解决的问题，例如判断两个区间内的子串是否相同
• 例如A的哈希值为1，B为2，C为3，D为4，则ABCD可以表示成$1·p^{3}+2·p^{2}+3·p^{1}+4·p^{0}$
• 如果知道了AB的哈希值为$1·p^{1}+2·p^{0}$，怎么求CD的哈希值呢？

• CD的哈希值就应该是$3·p^{1}+4·p^{0}$，可以发现这是ABCD哈希值中的一部分，我们需要把AB的哈希值乘上$p^{2}$，再把两者相减，就能获得CD的哈希值了

• 注意：
  1.不能映射为0，如果A的哈希值为0，那么AA的哈希值也为0，冲突
  2.根据经验，$p=131$或$p=13331$，且$Q=2^{64}$时，几乎不会发生冲突

Java代码

import java.io.*;
import java.util.*;
public class Main{
    private static final int N = 100010;
    private static long[] hash = new long[N];//存储字符串哈希值
    private static long[] p = new long[N];//求p的几次方
    private static final long Q = Long.MAX_VALUE;
    static long get(int l, int r){
        return hash[r]-hash[l-1]*p[r-l+1];
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        p[0] = 1;
        String s = br.readLine();
        char[] c = s.toCharArray();
        char[] str = new char[N];
        System.arraycopy(c,0,str,1,c.length);
        for(int i = 1; i <= n; i++){
            hash[i] = (hash[i-1] * 131 + str[i]) % Q;
            p[i] = p[i-1] * 131;
        }
        int l1,r1,l2,r2;
        while(m-- > 0){
            String[] s2 = br.readLine().split(" ");
            l1 = Integer.parseInt(s2[0]);
            r1 = Integer.parseInt(s2[1]);
            l2 = Integer.parseInt(s2[2]);
            r2 = Integer.parseInt(s2[3]);
            if(get(l1,r1) == get(l2,r2)) System.out.println("Yes");
            else System.out.println("No");
        }
    }
}