数据结构篇——哈希表

本次我们介绍数据结构中的哈希表，我们会从下面几个角度来介绍：

• 哈希表介绍
• 例题模拟散列表的两种方法
• 字符串前缀哈希法

哈希表介绍

首先我们先来简单介绍一下哈希表：

• 哈希表主要负责将空间较大的离散的数压缩为空间较小的数
• 例如我们将10-9~109之间的离散数可以压缩到10^5数组中

我们哈希表的主要算法为：

• 将x mod 10^5 得出余数，按照余数放在压缩后的数组中去
• 如果遇到冲突问题，我们采用两种方法来解决：拉链法和开放寻址法

我们给出两种解决方式：

• 拉链法：整个数组额外创建e[n]和ne[n]来当作链表存储点和下一个链表点来使用
• 开放寻址法：我们创造较多的数组，并按照正常方法放置，若当前点位已被放置就向后存放直到存放成功

模拟散列表的两种方法

首先我们给出例题：

• 维护一个集合，支持如下几种操作：
• I x，插入一个数 xx；
• Q x，询问数 xx 是否在集合中出现过；

我们分别给出两种解决方法：

/*拉链法*/

import java.util.Scanner;

public class Main {

    // 注意：这里的N尽量取到大于范围的第一个质数，因为质数是最不容易出现冲突的
    public static final int N = 100003;

    // 创建数组，创建拉链法的链表和下一个链表位(h存放的是e的位置，ne存放的当前e的下一个e的位置)
    public static int[] h = new int[N];
    public static int[] e = new int[N];
    public static int[] ne = new int[N];
    public static int idx = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        // 初始化定义
        for(int i = 0 ; i < N ; i++ ){
            h[i] = -1;
        }

        // 执行方法
        while (n-- > 0){
            String op = scanner.next();

            if(op.equals("I")){
                int x = scanner.nextInt();
                insert(x);
            }else{
                int x = scanner.nextInt();
                if(find(x)) System.out.println("Yes");
                else System.out.println("No");
            }


        }
    }

    public static void insert(int x){

        // 根据x判断其在h的位置(下面的运算是保证即使是负数其运算值也要为正数)
        int index = (x % N + N) % N;

        // insert操作（链表操作）
        e[idx] = x;
        ne[idx] = h[index];
        h[index] = idx;
        idx++;

    }

    public static boolean find(int x){

        // 根据x判断其在h的位置(下面的运算是保证即使是负数其运算值也要为正数)
        int index = (x % N + N) % N;

        // 循环判断
        for (int i = h[index]; i != -1; i = ne[i]){
            // 找到了返回true
            if (e[i] == x){
                return true;
            }
        }

        // 找不到返回false
        return false;
    }
}

/*开放寻址法*/

import java.util.Scanner;

public class Main {

    // 我们采用开放寻址法，需要将数据扩大一定倍数用于存放
    // 注意：这里的N尽量取到大于范围的第一个质数，因为质数是最不容易出现冲突的
    public static final int N = 200003;

    // 我们需要定义一个超出范围的数，作为数组的各部分的初始值
    public static final int NULL = 0x3f3f3f3f;

    // 我们只需要创建数组即可
    public static int[] h = new int[N];
    public static int idx = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        // 初始化定义
        for(int i = 0 ; i < N ; i++ ){
            h[i] = 0x3f3f3f3f;
        }

        // 执行方法
        while (n-- > 0){
            String op = scanner.next();
            int x = scanner.nextInt();
            int index = find(x);

            if(op.equals("I")){
                h[index] = x;
            }else{
                if(h[index] != NULL) System.out.println("Yes");
                else System.out.println("No");
            }

        }
    }

    public static int find(int x){

        // 根据x判断其在h的位置(下面的运算是保证即使是负数其运算值也要为正数)
        int index = (x % N + N) % N;

        // 开始寻找位置(为空时插入或者查找失败；为x时为查找成功)
        while (h[index] != NULL && h[index] != x){
            // 没有找到位置，向后移动；若到头回到开头继续匹配
            index++;
            if (index == N) index = 0;
        }

        // 找到位置
        return index;

    }
}

字符串前缀哈希法

我们首先来介绍一下字符串哈希：

• 字符串哈希和正常哈希方法相同
• 但是通常为了防止冲突，会采用特定的赋值哈希值的方法

我们来介绍P进制法赋值：

/*P进制法赋值介绍*/

// 我们首先给每个字符指定一个数，例如a=1，b=2，c=3...

// 然后我们需要指定一个p，作为进制数，让每一位在相应位置上乘上p的n次方

// 例如我们的"abc" = (1 * p^2)+(2 * p^1)+(3 * p^0)

/*P进制法赋值注意*/

// 首先我们需要注意字符尽量不为0，因为这样a，aa，aaa等的哈希值均为0，就会导致冲突

// 此外我们为了减少冲突，我们的p和q（进制以及哈希数组大小）应该设置为131和2^64,这是网上查询的最佳数据

在介绍过字符串哈希之后，我们来对习题进行更加细腻的分析：

• 给定一个长度n的字符串，再给定m个询问，每个询问包含四个整数 l1,r1,l2,r2。
• 请你判断 [l1,r1]和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
• 字符串中只包含大小写英文字母和数字。

我们首先进行分析：

/*字符串前缀法*/

// 我们进行字符串匹配并使用哈希方法就需要采用P进制辅助

// 但是为了一次性获得所有该字符串的哈希数据，我们可以采用字符串前缀法，也就是kmp思想

// 我们对于n的字符串，只需要求n次字符串的值（复杂）就可以根据特定的方法来求出内部字符串的哈希值

// 例如我们需要求1234 中的 34，我们只需要用1234哈希值来减去12*p^2的哈希值（需要乘上两者位数之差）

// 转换为代码就是 h[r] - (h[l-1] * p^(r-l+1))

我们给出问题解答代码：

import java.util.Scanner;

public class Main {

    // 首先我们需要一个N，P

    public static final int N = 1000010;
    public static final int P = 131;

    // 开的是long类型数组，本来是需要进行前缀hash求完之后需要进行模2的64次方来防止相同的冲突，可能超过我们给的数组大小
    // h存放数据，p存放p的n次方
    public static long[] h = new long[N];
    public static long[] p = new long[N];

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();
        String s = scanner.next();

        // p的0次方
        p[0] = 1;

        // 首先需要初始化，以及制作h前缀和哈希
        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,r1,l2,r2;

            l1 = scanner.nextInt();
            r1 = scanner.nextInt();
            l2 = scanner.nextInt();
            r2 = scanner.nextInt();

            // 分别获得hash值，然后比较
            long hashcode1 = get(l1,r1);
            long hashcode2 = get(l2,r2);

            if (hashcode1 == hashcode2){
                System.out.println("Yes");
            }else {
                System.out.println("No");
            }
        }

    }

    // 获得区间哈希值，采用字符串前缀和法，用前缀和之差来获得当前区间的哈希值
    public static long get(int l,int r){
        return h[r] - h[l-1]*p[r-l+1];
    }
}

好的，关于数据结构篇的哈希表就介绍到这里，希望能为你带来帮助~