当前位置：首页 > news >正文

Acwing Hash表

news 2024/9/20 17:07:18

哈希表的作用：把一个比较大的空间，通过一个函数映射到一个比较小的空间
一般做哈希运算时，取一个质数作为模，会使得冲突的概率降低。
哈希表的冲突解决方法：

拉链法
开放寻址法

下面详细介绍这两种方法的原理及其实现：

1.拉链法

创建一个数组h[],插入一个值时通过哈希函数映射到数组对应位置，每个位置维护一个链表，映射到相同位置加入当前链表中。
数组h[i]类似于链表的头指针，存储的是其下链表的第一个结点x的数组下标**，而不是结点的值x，取值范围0~N，所以可以让数组h的默认值为-1，以此判断该位置下是否为空

插入操作：采用头插法，根据哈希函数计算哈希值，每次冲突的值，插入到链表的第一个位置；
查询操作：根据哈希值找到对应头指针即对应链表，再对链表遍历判断；
删除操作：删除操作并不是真正的删除该元素，而是设置一个标记值，来表示该位置的值已被删除（用得少）。
板子：

const int N = 100003; // 大于10^5的最小质数，作为哈希表的大小int h[N], e[N], ne[N], idx = 0; 
// h[] 用于存储每个哈希值对应的链表头结点
// e[] 用于存储插入的值
// ne[] 用于存储每个元素的下一个节点的索引
// idx 是当前插入元素的索引// 插入操作，使用拉链法实现
void insert(int x){int k = (x % N + N) % N; // 计算哈希值，处理负数时确保结果为正数e[idx] = x;              // 将x存入数组e，idx是当前存储的索引ne[idx] = h[k];          // 将当前元素的下一个节点设置为链表的第一个节点h[k] = idx++;            // 将哈希表h[k]指向当前元素，并更新idx
}// 查找操作，查找元素x是否存在
bool find(int x){int k = (x % N + N) % N; // 计算哈希值for(int i = h[k]; i != -1; i = ne[i]){ // 遍历哈希表k对应的链表if(e[i] == x) return true;         // 如果找到，返回true}return false;                          // 没找到，返回false
}

哈希表常用取余法，代码实现找一个大于等于N且最小的质数：

int get_Prime(int N){for(int i = N;;i++){bool flag = true;for(int j = 2; j * j <= i;j ++){if(i % j== 0){flag = false;break;}}if(flag){return i;break;}}
}

2.开放寻址法：

开放寻址法：当冲突发生时，使用某种探测算法（得出一个偏移量）在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。探测法有线性探测法、平方探测法、双散列法、伪随机序列。这里直接使用线性探测法，即冲突则自增1。

数组h[]存储的时具体的节点值x，而x的取值范围是 $10^9 --10^9$ .故应该让数组x的默认值不在x的取值范围内（定义null = 0x3f3f3f3f),这样才好判断h[k[位置上是否为空（注意和拉链法区分）

查找和查询操作合为一个find()函数：首先根据哈希函数计算的哈希值查找当前元素是否在初始位置。若该位置为空，则在这个位置插入该元素；若不为空且与该元素不等，则向后继续查找，直到找到该元素或有空位置则插入该元素。最后返回该位置。

板子：

const int N = 200003, null = 0x3f3f3f3f; // N为哈希表的大小，null为标志无效值的常量
int h[N]; // 哈希表，存储元素// 开放寻址法查找函数
// 如果x在哈希表中，返回x的下标；
// 如果x不在哈希表中，返回x应该插入的位置
int find(int x) {int k = (x % N + N) % N; // 计算哈希值，处理负数使其为正while(h[k] != null && h[k] != x) { // 当位置不为空且不等于x时，进行线性探测k++; // 如果发生冲突，继续探测下一个位置if(k == N) k = 0; // 如果到达末尾，回到哈希表开头}return k; // 返回找到的插入位置或x所在的位置
}

好的，下面给出一道题目，我们采用两种方法解答：

Acwing 840. 模拟散列表
在这里插入图片描述
输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

具体实现（2种）：

//拉链法
#include <iostream>
#include <cstring>using namespace std;const int N = 100003; // 大于10^5的最小质数，作为哈希表的大小int h[N], e[N], ne[N], idx = 0; 
// h[] 用于存储每个哈希值对应的链表头结点
// e[] 用于存储插入的值
// ne[] 用于存储每个元素的下一个节点的索引
// idx 是当前插入元素的索引// 插入操作，使用拉链法实现
void insert(int x){int k = (x % N + N) % N; // 计算哈希值，处理负数时确保结果为正数e[idx] = x;              // 将x存入数组e，idx是当前存储的索引ne[idx] = h[k];          // 将当前元素的下一个节点设置为链表的第一个节点h[k] = idx++;            // 将哈希表h[k]指向当前元素，并更新idx
}// 查找操作，查找元素x是否存在
bool find(int x){int k = (x % N + N) % N; // 计算哈希值for(int i = h[k]; i != -1; i = ne[i]){ // 遍历哈希表k对应的链表if(e[i] == x) return true;         // 如果找到，返回true}return false;                          // 没找到，返回false
}int main(){memset(h, -1, sizeof h); // 初始化哈希表h，令所有值为-1，表示链表为空int n; // 操作数cin >> n;while(n--){ // 处理n个操作char op[2]; // 操作符int x;      // 操作的数值cin >> op >> x;if(op[0] == 'I') insert(x); // 插入操作else { // 查找操作if(find(x)) puts("Yes"); else puts("No");         }}return 0;
}

//开放寻址法
#include <iostream>
#include <cstring>using namespace std;const int N = 200003, null = 0x3f3f3f3f; // N为哈希表的大小，null为标志无效值的常量
int h[N]; // 哈希表，存储元素// 开放寻址法查找函数
// 如果x在哈希表中，返回x的下标；
// 如果x不在哈希表中，返回x应该插入的位置
int find(int x) {int k = (x % N + N) % N; // 计算哈希值，处理负数使其为正while(h[k] != null && h[k] != x) { // 当位置不为空且不等于x时，进行线性探测k++; // 如果发生冲突，继续探测下一个位置if(k == N) k = 0; // 如果到达末尾，回到哈希表开头}return k; // 返回找到的插入位置或x所在的位置
}int main() {//memset按字节赋值，int4个字节，每个字节赋值0x3f，则h默认值就为0x3f3f3f3f 即nullmemset(h, 0x3f, sizeof h); // 初始化哈希表，所有位置都标记为nullint n; // 操作次数cin >> n;while(n--) {char op[2]; // 操作类型int x; // 操作的数值cin >> op >> x;int k = find(x); // 通过find函数得到x的位置if(op[0] == 'I') h[k] = x; // 插入操作，将x放入找到的位置else {if(h[k] != null) puts("Yes"); // 如果h[k]不是null，说明x在哈希表中else puts("No"); // 否则x不在哈希表中}}return 0;
}