算法基础班–第二章–14.一般哈希模板
算法模板
- 模板一:拉链法
- 模板二:开放寻址法
模板1:拉链法处理哈希冲突
int h[N], e[N], ne[N], idx
向哈希表中插入一个数
void insert(int x) {
int k = (x % N + N) % N;
e[idx] = x; //使用的就是单链表的头插法
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 = ne[i])
if (e[i] == x) return true; //在对应的单链表中找是否存在x
return false;
}
模板2:开放寻址法处理哈希冲突
int h[N];
//如果x在哈希表中,返回x的下标;如果x不在哈希表中,返回x应该插入的位置
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;
}
本题完整代码
使用模板一:拉链法
#include <iostream>
#include <memory.h>
using namespace std;
const int N = 100003; //100003大于100000的第一个质数,用下面代码求出来的
int h[N], e[N], ne[N], idx; // 给哈希表开一个槽用h[N]表示,每个槽拉一个链,链上存两个东西,一个值与下一个位置
// 拉链法处理哈希冲突
void insert(int x) {
int k = (x % N + N) % N;
e[idx] = x; //使用的就是单链表的头插法
ne[idx] = h[k];
h[k] = idx++;
}
/*
x取 -10^9 ~ 10^9,用一个哈希函数把x映射到0~N,
C++ 中负数取模与数学中负数取模结果不一样,
数学中-10 % 3 = -4...余2,C++中余数是-1,
为了避免余数是负的C++这样做(+N)%N,-10%3=-1,(-1+3)%3=2
*/
//判断x是否已经在hash表中,如果在就返回true,否则返回false
bool 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; //在对应的单链表中找是否存在x
return false;
}
int main () {
int n;
scanf("%d", &n);
memset(h, -1, sizeof(h)); //先把所有的槽清空,单链表中空指针用-1
while (n--) {
char op[2];
int x;
scanf("%s%d", op, &x); //用%s读入字符串
if (*op == 'I') insert(x); // 这里的*op 就是 op[0]的意思
else {
if (find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
使用模板二:开放寻址法
#include <iostream>
#include <string.h>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f; //null 是大于10^9的数,不在x范围内
// 开放寻址法只用开一个数组,N = 2N,首先找到大于200000的最小质数200003
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;//如果k不是x在哈希表中应该存的位置,则此时h[k] == null......No
//如果k是x在哈希表中的位置,则此时h[k] == x..............Yes
}
int main() {
int n;
scanf("%d", &n);
memset(h, 0x3f, sizeof h);//memset() 是按字节存储,不是按数存,int 有4个字节,就会把4个字节全变成0x3f,此时每个数都是4个0x3f = 0x3f3f3f3f
while (n--) {
char op[2];
int x;
scanf("%s%d", op, &x);
int k = find(x);//k代表的含义有两种,这两种含义分别决定了"Q x"操作应该输出Yes或No
if (*op == 'I') h[k] = x;
else {
if (h[k] != null) puts("Yes"); //k的两种含义 if else
else puts("No");
}
}
return 0;
}
// 这段代码是用来找大于100000的第一个质数
#include <iostream>
#include <memory.h>
#include <cstdio>
using namespace std;
int main () {
for (int i = 100000; ; i++){
bool flag = true;
for (int j = 2; j * j <= i; j++) //枚举i的所有积因子
if (i % j == 0) {
flag = false;
break;
}
if (flag) { //flag==true说明是质数
cout << i << endl;
break;
}
}
return 0;
}