7、哈希表
哈希表最主要的作用就是把一个比较庞大的空间或者值域 映射到比较小的值域 (0-n)
就是将-10^9 ~10^9 映射到 0 ~10^5
一、存储结构
映射的方法可以是 h(x) = x mod 10^5
但是这样映射会出现一个问题 可能会有重复的数字出现
所以就引出了两个方法 开放寻址法 和 拉链法
1、开放寻址法
也开一个一维数组 但是一维数组的长度要是题目所给数据的2-3倍
h(x) = k
从第k个数字开始去找 如果已经存在了 就去找下一个
2、拉链法
开一个一维数组去存储值 比如映射到0~10^5
则开一个长度为10^5的数组
如图所示 当11和23都映射到3这个位置的时候
可以在3的下面开一个拉链 去记录所有映射到这个位置上的数字
题目:模拟散列表
维护一个集合,支持如下几种操作:
I x,插入一个数 x;
Q x,询问数 x 是否在集合中出现过;
现在要进行 n 次操作,对于每个询问操作输出对应的结果。
输入格式:
第一行包含整数 n,表示操作数量。
接下来 n 行,每行包含一个操作指令,操作指令为I x,Q x中的一种。
输出格式:
对于每个询问指令Q x,输出一个询问结果,如果 x 在集合中出现过,则输出 Yes,否则输出 No。
每个结果占一行。
数据范围:
1≤n≤10^5
-10^9<=x <= 10^9
输入样例:
5
I 1
I 2
I 3
Q 2
Q 5
输出样例:
Yes
No
代码一(拉链法):
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010;
int h[N];
int e[N], ne[N], idx;
void insert(int x)
{
//首先先把x映射到数组中去
int k = (x % N + N) % N;
e[idx] = k;
ne[idx] = h[k];
h[k] = idx++;
}
bool find(int x)
{
//同理 也是先将其映射到数组中
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i++)
{
if (e[i] = k) return true;
}
return false;
}
int main()
{
int n; cin >> n;
memset(h,-1,sizeof h);
while (n--)
{
char op[2];
scanf("%s",op);
if (op[0] == 'I')
{
int x; cin >> x;
insert(x);
}
else {
int x; cin >> x;
if (find(x)) cout << "Yes";
else cout << "No";
}
}
return 0;
}
二、字符串哈希的方式
O(1)
快速判断两个字符串是否相等
就可以用该方法
字符串前缀哈希法
给定一个字符串
首先预处理所有前缀的哈希值
(如何来定义每一个前缀的哈希值)
p进制
假设A-Z个字母 求出这个数组的十进制数字
(相加的结果可能过于大 所以mod上一个数字) 、
就可以把整个数字映射到0 - Q-1上
注意
1、不能够映射成0
如果可以的话 A -> 0 AA-> 0 重复了
2、不存在冲突的情况
p = 131 或者13331
Q = 2^64
这样取值 在一般情况下 可以假定不会出现冲突
怎么求出 L-R这一段的哈希值
把1-R的所有的数字 看成是p进制的数字 左边是高位 右边是低位
即 在h[R]中 R就是第0位 1就是R-1位
h[L-1] 中 L-1就是第0位 1是L-2位
已知从1-R的哈希值h[R] = p^(r-1) ….p^0
和1-L-1 的哈希值 h[L-1] = p^(l-2) …….p ^0
因此让h[L-1] * p^(R-L+1) =》作用是让h[L]往右移动若干位 与h[R]对齐
*=》h[R] - h[L-1] p^(R-L+1)
思路整理
- 把字符串看成是一个 P 进制数,每个字符的 ASCII 码对应数的一位
- ASCII 范围 0 - 127,最少 128 进制,经验上取 131 或 13331 冲突率低
- 字符串很长,对应的数太大,通过模 2^64 把它映射到 [0, 2^64 - 1]
- 用 unsigned long long 存储,溢出相当于对 2^64 取模,省略了手动运算
- 该方法的好处是,可以利用前缀哈希直接求出子串哈希(减去高位)
hash(DEF) = hash(ABCDEF) - hash(ABC) x P^3
1 2 3 4 5 6
A B C D E F
1xP^5 + 2xP^4 + 3xP^3 + 4xP^2 + 5xP^1 + 6xP^0
D E F
4xP^2 + 5xP^1 + 6xP^0
A B C
1xP^2 + 2xP^1 + 3xP^0
题目描述 字符串哈希
给定一个长度为
标签:输出,映射,10,int,哈希,字符串 From: https://blog.csdn.net/weixin_73378557/article/details/143244900