数据结构篇——哈希表
本次我们介绍数据结构中的哈希表，我们会从下面几个角度来介绍：
- 哈希表介绍
- 例题模拟散列表的两种方法
- 字符串前缀哈希法
哈希表介绍
首先我们先来简单介绍一下哈希表：
- 哈希表主要负责将空间较大的离散的数压缩为空间较小的数
- 例如我们将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]; } } 结束语
好的，关于数据结构篇的哈希表就介绍到这里，希望能为你带来帮助~
