AcWing 840. 模拟散列表
原题链接
简单
模拟散列表
拉链法
#include <iostream>
#include <string.h>
using namespace std;
const int N = 1e5 + 10;
// head[] 里面存储的是链表的第一个节点的下标
int head[N], e[N], ne[N], idx;
// 哈希函数
int _hash(int n) {
return (n % N + N) % N;
}
void insert(int x) {
int k = _hash(x);
e[idx] = x;
ne[idx] = head[k];
head[k] = idx++;
}
bool find(int x) {
int k = _hash(x);
for (int i = head[k]; i != -1 ; i=ne[i]) {
if (e[i] == x) {
return true;
}
}
return false;
}
/**
* acwing 840-模拟哈希表
* @return
*/
int main() {
int n;
cin >> n;
memset(head, -1, sizeof head);
while (n--) {
string op;
int x;
cin >> op >> x;
if (op == "I") {
insert(x);
} else if (op == "Q") {
if (find(x)) {
puts("Yes");
} else {
puts("No");
}
}
}
return 0;
}
开放定址法
// 开放定址法
// Created by 木已成舟 on 2021/1/27.
//
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e5 + 3;
// 规定空指针为0x3f3f3f3f,这是一个大于10e9的数,视数据规模而定
const int null = 0x3f3f3f3f;
int h[N];
// hash函数
int _hash(int x) {
return (x % N + N) % N;
}
void insert(int x) {
int k = _hash(x);
// 向后探寻,直到找到null
while (h[k] != null) {
k = (k + 1) % N;
}
h[null] = x;
}
bool find(int x) {
int k = _hash(x);
while (h[k] != null) {
if (h[k] == x) return true;
k = (k + 1) % N;
}
return false;
}
int main() {
int n;
cin >> n;
// memset 赋值的时候是1个字节的赋值
memset(h, 0x3f, sizeof h);
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;
}