2、散列表&字符串哈希

AcWing 840. 模拟散列表

AcWing 841. 字符串哈希

开放寻址法

import java.io.*;
import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.sanliebiao();
    }

    int N = 200003,none=0x3f3f3f;
    int h[] = new int[N];

    int find(int x){
        int t=(x%N+N)%N;
        while(h[t]!=none&&h[t]!=x){
            t++;
            if(t==N) t=0;
        }
        //如果存在，返回的是寻址法后的位置
        //如果不存在，返回的是t本身，会发现是none
        return t;
    }
    //开放寻址法
    void sanliebiao(){
        Arrays.fill(h,none);
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        while(n-->0){
            String op=sc.next();
            int k=sc.nextInt();
            int fk=find(k);
            if(op.equals("I")){
                h[fk]=k;
            }
            if(op.equals("Q")){
                if(h[fk]==none) System.out.println("No");
                else System.out.println("Yes");
            }
        }
    }
}

拉链法

import java.io.*;
import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.sanliebiao();
    }

    int N = 100003;
    int h[] = new int[N];
    int e[] = new int[N];
    int ne[] = new int[N];
    int idx = 0;//唯一的地址值

    void insert(int x) {
        int t = (x % N + N) % N;
        //不管如何链表先去存储x
        //e[idx]已经是新开的数组位置
        e[idx] = x;
        //链表下一个位置存储h[t]，如果h[t]没有存储过的话默认-1
        ne[idx] = h[t];
        //h[t]存储的是地址，方便找到尾元素
        h[t] = idx++;
        //这里的h[t]就相当于单链表的head
    }

    boolean find(int x) {
        int t = (x % N + N) % N;
        //h[t]就相当于head，从头结点向下寻找
        for (int i = h[t]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;
        return false;
        //false表示还没冲突，此位置是空缺的
    }

    //拉链法
    void sanliebiao() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Arrays.fill(h,-1);
        while (n-- > 0) {
            String op = sc.next();
            int k = sc.nextInt();
            if (op.equals("I")) insert(k);
            else {
                //没冲突
                if (find(k) == false) {
                    System.out.println("No");
                } else {
                    System.out.println("Yes");
                }
            }
        }
    }
}

字符串哈希

import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args){
        Main main=new Main();
        main.zifuchuanhash();
    }
    //开的是long类型数组，本来是需要进行前缀hash求完之后需要进行模2的64次方来防止相同的冲突，可能超过我们给的数组大小
    int N = 100010,P = 131;//p是进制数，经验值
    long[] h = new long[N];//这是存放hash前缀值得数组
    long[] p = new long[N];//这是存放p的n次方的数组
    public long get(int l,int r){//这里是将运用了一点前缀和公式的方式进行计算
        //求l-r区间的hash值，就要用h[r] - h[l-1],因为两者位数不用需要让h[l-1]向左边移到跟h[r]对齐
        //就比如求1234的3-4区间位，1234 - 12,12左移然后就让12*10^(4-3+1)=12*10^2=1200,然后1234-1200 = 34,这样进行计算出来
        //然后本题是p进制，所以需要将上面公式中的10换成p就行了
        //h[0] = 0
        //h[1] = h[i-1] * P + str[1] = 0*P+a = a
        //h[2] = a * P + b
        //h[3] = (a*P+b)*P+c = a*p[2]+b*P+c
        //h[4] = (a*p[2]+b*P+c)*P+d = a*p[3]+b*p[2]+c*P+d
        //比如abcd求3-4区间位，就是让h[d]-h[b]，h[b]位数不用需要向左移对齐h[d],
        //h[2]*P^(4-3+1)=(a*P+b)*P^2 = a*P^3+b*P^2
        //然后就让h[d] - h[b]求出34区间值,(a*p[3]+b*p[2]+c*P+d) - (a*P^3+b*P^2) = c*P+d
        return h[r] - h[l-1]*p[r-l+1];
    }
    void zifuchuanhash(){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        String s = scan.next();
        p[0] = 1;//这个是p的0次方的值，需要单独写出来，非常重要
        for(int i = 1 ; i <= n ; i++ ){
            p[i] = p[i-1] * P;//这里对应每一个下标对应对应P的多少次方
            h[i] = h[i-1] * P + s.charAt(i-1);//这里是公式，预处理前缀哈希的值，因为是P进制，所以中间乘的是P
        }
        while(m -- > 0){
            int l1 = scan.nextInt();
            int r1 = scan.nextInt();
            int l2 = scan.nextInt();
            int r2 = scan.nextInt();
            //判断两个区间是不是相同,用get的方法返回值一样说明区间的hash值是一样的
            if(get(l1,r1) == get(l2,r2)) System.out.println("Yes");
            else System.out.println("No");
        }
    }
}