算法模板（Java版）_哈希表

@ZZHow(ZZHow1024)

哈希表

• 存储结构
  • 拉链法：在找到的位置向下拉一条单链表
  • 开放寻址法：从找到的位置开始继续向后寻找空的位置
• 字符串哈希方式：
  • 把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字。
    采用字符的 ASCII 码乘上 P 的次方来计算哈希值。
  • 映射公式 (X1 × Pn − 1 + X2 × Pn − 2 + ⋯ + Xn − 1 × P1 + Xn × P0) % Q
  • 注意点：
    1. 任意字符不可以映射成 0，否则会出现不同的字符串都映射成 0 的情况，比如A, AA, AAA 皆为 0。
    2. 冲突问题：通过设置 P(131 或 13331) , Q($2^{64}$)的值，一般可以理解为不产生冲突，P 和 Q 是经验值。

模拟散列表

• 例题：AcWing 840. 模拟散列表

1. 寻找质数

public class Main {static int N = 100000;public static void main(String[] args) {for (int i = N;;i++) {boolean flag = true;for (int j = 2; j * j <= i; j++) {if (i % j == 0) {flag = false;break;}}if (flag) {System.out.println("大于100000的第一个质数是：" + i);break;}}}
}

1. 处理哈希冲突

   1. 拉链法

   import java.util.Scanner;public class Main {static int N = 100003;static int[] h = new int[N];static int[] e = new int[N];static int[] ne = new int[N];static int idx;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);for (int i = 0; i < h.length; i++)h[i] = -1;int n = scanner.nextInt();while (n-- != 0) {String op = scanner.next();switch (op) {case "I": {int x = scanner.nextInt();insert(x);break;}case "Q": {int x = scanner.nextInt();if (find(x))System.out.println("Yes");elseSystem.out.println("No");break;}}}}public static void insert(int x) {int k = (x % N + N) % N; // 确保映射到正数// 单链表头插法e[idx] = x;ne[idx] = h[k];h[k] = idx++;}public static boolean find(int x) {int k = (x % N + N) % N; // 确保映射到正数// 单链表查找数据for (int i = h[k]; i != -1; i = ne[i])if (e[i] == x)return true;return false;}
   }
   

   b. 开放寻址法

   import java.util.Scanner;public class Main {static final int N = 200003;static Integer[] h = new Integer[N];public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();while (n-- != 0) {String op = scanner.next();int x = scanner.nextInt();int k = find(x);switch (op) {case "I": {h[k] = x;break;}case "Q": {if (h[k] == null)System.out.println("No");elseSystem.out.println("Yes");break;}}}}public static int find(int x) {int k = (x % N + N) % N;while (h[k] != null && h[k] != x) {k++;if (k == N)k = 0;}return k;}
   }
   

字符串哈希

• 例题：AcWing 840. 模拟散列表

import java.io.*;
import java.util.*;public class Main {static final int N = 100010;static final int P = 131;static final long Q = Long.MAX_VALUE;static long[] h = new long[N];static long[] p = new long[N];static char[] c = new char[N];public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));String[] lines = br.readLine().split(" ");int n = Integer.parseInt(lines[0]);int m = Integer.parseInt(lines[1]);c = (" " + br.readLine()).toCharArray();h[0] = 0;p[0] = 1;for (int i = 1; i <= n; i++) {p[i] = (p[i - 1] * P) % Q;h[i] = (h[i - 1] * P + c[i]) % Q;}while (m-- != 0) {lines = br.readLine().split(" ");int l1 = Integer.parseInt(lines[0]);int r1 = Integer.parseInt(lines[1]);int l2 = Integer.parseInt(lines[2]);int r2 = Integer.parseInt(lines[3]);if (get(l1, r1) == get(l2, r2))bw.write("Yes\n");elsebw.write("No\n");}br.close();bw.close();}public static long get(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1];}
}