数据结构篇——哈希表

时间:2022-11-21 09:06:20

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

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

哈希表介绍

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

  • 哈希表主要负责将空间较大的离散的数压缩为空间较小的数
  • 例如我们将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];
    }
}

结束语

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