資料結構篇——雜湊表

本次我們介紹資料結構中的雜湊表，我們會從下面幾個角度來介紹：

• 雜湊表介紹
• 例題模擬雜湊表的兩種方法
• 字串字首雜湊法

雜湊表介紹

首先我們先來簡單介紹一下雜湊表：

• 雜湊表主要負責將空間較大的離散的數壓縮為空間較小的數
• 例如我們將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];
    }
}

結束語

好的，關於資料結構篇的雜湊表就介紹到這裡，希望能為你帶來幫助~