T O P

[资源分享]     数据结构篇——哈希表

  • By - 楼主

  • 2022-11-21 10:10:43
  • 数据结构篇——哈希表

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

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

    哈希表介绍

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

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

    结束语

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

    本帖子中包含资源

    您需要 登录 才可以下载,没有帐号?立即注册