数据结构 - 哈希表（开放地址法、拉链法、字符串前缀哈希）

本文主要是介绍数据结构 - 哈希表（开放地址法、拉链法、字符串前缀哈希），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

本篇博客将介绍哈希表的存储方式（拉链法、开放地址法），以及一类十分重要的应用字符串哈希，字符串哈希可以取代KMP功能十分强大，而且相当简化。那么我们首先要知道什么是哈希表？？？

哈希表：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表
简单来说也就是：通过取模运算，将本来范围极大的数据，映射到较小的范围里，当存在冲突是通过拉链法或者开放地址法解决，方便了大范围离散数据的存储和查找等操作

Part 1：模拟散列表

1.题目描述

维护一个集合，支持如下几种操作：

1. I x，插入一个整数 x；
2. Q x，询问整数 x 是否在集合中出现过；

现在要进行 N 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤N≤10⁵
−10⁹≤x≤10⁹

输入样例

5
I 1
I 2
I 3
Q 2
Q 5

输出样例

Yes
No

2.算法（开放地址法）

• 开放寻址法采用hash函数找到在hash数组中对应的位置，如果该位置上有值，并且这个值不是寻址的值，则出现冲突碰撞，需要解决冲突方案，该算法采用简单的向右继续寻址来解决问题

#include <cstring>
#include <iostream>using namespace std;//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 2e5 + 3;        //大于数据范围的第一个质数
const int null = 0x3f3f3f3f;  //规定空指针为 null 0x3f3f3f3fint h[N];//如果这个位置是空的, 则返回的是它应该存储的位置;否则，返回它已经存储的位置
int find(int x) 
{int t = (x % N + N) % N;while (h[t] != null && h[t] != x) {t++;if (t == N) {t = 0;}}return t;
}int n;int main() 
{cin >> n;memset(h, 0x3f, sizeof h);  //规定空指针为 0x3f3f3f3fwhile (n--) {string op;int x;cin >> op >> x;if (op == "I") {h[find(x)] = x;} else {if (h[find(x)] == null) puts("No");else puts("Yes");}}return 0;
}

3.算法（拉链法）

• 在每个位置拉一条链表，发生冲突直接在该位置对应的链表里添加即可

#include <cstring>
#include <iostream>using namespace std;const int N = 1e5 + 3;  // 取大于1e5的第一个质数，取质数冲突的概率最小 可以百度// 开一个槽 h
int h[N], e[N], ne[N], idx;  //邻接表void insert(int x) 
{// c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx++;
}bool find(int x) 
{//用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数int k = (x % N + N) % N;for (int i = h[k]; i != -1; i = ne[i]) {if (e[i] == x) {return true;}}return false;
}int n;int main() 
{cin >> n;memset(h, -1, sizeof h);  //将槽先清空 空指针一般用 -1 来表示while (n--) {string op;int x;cin >> op >> x;if (op == "I") {insert(x);} else {if (find(x)) puts("Yes");else puts("No");}}return 0;
}

Part 2：字符串哈希

1.题目描述

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2]这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 n 和 m，表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 1 开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤10⁵

输入样例

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例

Yes
No
Yes

2.算法（字符串前缀哈希）

• 方法介绍：全称字符串前缀哈希法，把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字。对形如 X₁X₂X₃⋯X_n−1X_n 的字符串,采用字符的ascii 码乘上 P 的次方来计算哈希值。映射公式 (X₁×Pⁿ⁻¹+X₂×Pⁿ⁻²+⋯+X_n−1×P¹+X_n×P⁰)modQ
• 注意点1：任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0
• 注意点2：冲突问题：通过巧妙设置P (131 或 13331) , Q (264)的值，一般可以理解为不产生冲突，所以不必考虑冲突情况
• 问题转化：问题是比较不同区间的子串是否相同，就转化为对应的哈希值是否相同。求一个字符串的哈希值就相当于求前缀和，求一个字符串的子串哈希值就相当于求部分和
• 公式：前缀和公式 h[i+1]=h[i]×P+s[i]，h为前缀和数组，s为字符串数组。区间和公式 h[l,r]=h[r]−h[l−1]×P^r−l+1
• 举例理解：区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，乘上 P²， 把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。

#include<iostream>
#include<cstdio>
#include<string>using namespace std;typedef unsigned long long ULL;
const int N = 1e5+5,P = 131;//131 13331
ULL h[N],p[N];// h[i]前i个字符的hash值
// 字符串变成一个p进制数字，体现了字符+顺序，需要确保不同的字符串对应不同的数字
// P = 131 或  13331 Q=2^64，在99%的情况下不会出现冲突
// 使用场景： 两个字符串的子串是否相同
ULL query(int l,int r)
{return h[r] - h[l-1]*p[r-l+1];
}int main()
{int n,m;cin>>n>>m;string x;cin>>x;//字符串从1开始编号，h[1]为前一个字符的哈希值p[0] = 1;h[0] = 0;for(int i=0;i<n;i++){p[i+1] = p[i]*P;            h[i+1] = h[i]*P +x[i];      //前缀和求整个字符串的哈希值}while(m--){int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;if(query(l1,r1) == query(l2,r2)) printf("Yes\n");else printf("No\n");}return 0;
}

这篇关于数据结构 - 哈希表（开放地址法、拉链法、字符串前缀哈希）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---