【蓝桥杯集训8】哈希表专题（3 / 3）

目录

手写哈希表

1、开放寻址法

2、拉链法

字符串前缀哈希表法

2058. 笨拙的手指 - 哈希表 + 秦九韶算法（进制转换）+ 枚举

秦九韶算法——将x进制数转化为十进制数

---

手写哈希表

活动 - AcWing

1、开放寻址法

设 h(x)=k，也就是 x 的哈希值为 k

如果在 hash[k]的位置已经有元素，持续往后遍历直到找到 >x（询问）或为空（插入）为止

注意开放寻址法一般会把数组开到数据范围的 2−3 倍，能提高效率

import java.util.*;class Main
{static int N=200003,nul=0x3f3f3f3f; //质数static int[] h=new int[N];public static int find(int x){int k=(x%N+N)%N;while(h[k]!=nul&&h[k]!=x) //如果该坑位不为空且该坑位不为x（如果x已经存过就不存了）{k++;if(k==N) k=0;}return k; //如果找到x，则返回x所在的位置//如果没有找到x，则返回x应该存放的位置}public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();Arrays.fill(h,nul);while(n-->0){String s=sc.next();int x=sc.nextInt();int k=find(x);if(s.equals("I")) h[k]=x;else if(s.equals("Q")){if(h[k]!=nul) System.out.println("Yes");else System.out.println("No");}}}
}

2、拉链法

设 h(11)=3，h(23)=3 ，这就是一种冲突

我们可以设一个数组h，也就是哈希的结果

对于每一个结果k，建立一个链表

把映射为 k 的所有数 x 都放在 h[k] 这个链表里

import java.util.*;class Main
{static int N=100003; //质数static int[] h=new int[N],e=new int[N],ne=new int[N];static int idx;public static void insert(int x){int k=(x%N+N)%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;}public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();Arrays.fill(h,-1);while(n-->0){String s=sc.next();int x=sc.nextInt();if(s.equals("I")) insert(x);else if(s.equals("Q")){if(find(x)) System.out.println("Yes");else System.out.println("No");}}}
}

 

字符串前缀哈希表法

把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字

对形如  的字符串，采用字符的ascii 码乘上 P 的次方来计算哈希值

映射公式 

注意：

• 任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0
• 通过巧妙设置P (131 或 13331) , Q ()的值，一般可以理解为不产生冲突

比较不同区间的子串是否相同，就转化为对应的哈希值是否相同

求一个字符串的哈希值就相当于求前缀和，求一个字符串的子串哈希值就相当于求部分和

字符串前缀和公式：

h[i] = h[i-1]*P + s[i];

区间和公式：

区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，
乘上  把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值

活动 - AcWing

题目：

import java.util.*;class Main
{static int N=100010;static long[] h=new long[N],p=new long[N];static int P=131;public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt();String s="/"+sc.next();//下标从1开始p[0]=1;for(int i=1;i<=n;i++){p[i]=p[i-1]*P;h[i]=h[i-1]*P+s.charAt(i);}while(m-->0){int l1=sc.nextInt(),r1=sc.nextInt();int l2=sc.nextInt(),r2=sc.nextInt();long h1=h[r1]-h[l1-1]*p[r1-l1+1];long h2=h[r2]-h[l2-1]*p[r2-l2+1];System.out.println(h1==h2?"Yes":"No");}}
}

2058. 笨拙的手指 - 哈希表 + 秦九韶算法（进制转换）+ 枚举

2058. 笨拙的手指 - AcWing题库

题目：

第一行给你一个N的二进制表示，其中有一位是错误的

第二行给你一个N的三进制表示，其中有一位是错误的

输出N的正确十进制值（题目保证一定有唯一解）

思路：

枚举二进制数a的所有换1位的情况，转化为十进制值存入哈希表

枚举三进制数b的所有换1位情况，转化为十进制后在哈希表中查询是否存在 

因为题目保证一定有唯一解，所以两者交集即为答案

因此如果查询到，则输出

秦九韶算法——将x进制数转化为十进制数

public static int get(String s,int x)
{int res=0;for(int i=0;i<s.length();i++){char t=s.charAt(i);res=res*x + t-'0';}return res;
}

import java.util.*;class Main
{static int N=100010;public static int get(char[] s,int x)//将x进制数s转化为十进制数{//秦九韶算法int res=0;for(int i=0;i<s.length;i++){res=res*x+s[i]-'0';}return res;}public static void main(String[] args){Scanner sc=new Scanner(System.in);char[] a=sc.next().toCharArray();char[] b=sc.next().toCharArray();Set<Integer> st=new HashSet<>();for(int i=0;i<a.length;i++){a[i]^=1;st.add(get(a,2));a[i]^=1;}for(int i=0;i<b.length;i++){char t=b[i];for(int j=0;j<3;j++) //将这一位换成除了本身的其他数if(t-'0'!=j){b[i]=(char)(j+'0');int tp=get(b,3);if(st.contains(tp)){System.out.print(tp);return;}}b[i]=t; //换完该位要恢复现场 继续换下一位}}
}