數據結構篇——哈希表
數據結構篇——哈希表
本次我們介紹數據結構中的哈希表，我們會從下面幾個角度來介紹：
- 哈希表介紹
- 例題模擬散列表的兩種方法
- 字符串前綴哈希法
哈希表介紹
首先我們先來簡單介紹一下哈希表：
- 哈希表主要負責將空間較大的離散的數壓縮為空間較小的數
- 例如我們將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];
}
}
結束語
好的，關於數據結構篇的哈希表就介紹到這裡，希望能為你帶來幫助~
