哈希表的作用
本题运用哈希表来做的思路
- 把数据范围在
-1e9 到 1e9
的数(个数不超过1e5
),映射到[0, 10^5)
。跟离散化有点像,不同之处在于离散化是保序的,即离散化操作前需要排序
Q1:如何进行映射?
x mod
上10^5
即可,但是一般我们不会直接草率的使用10^5
,而是选择一个比10^5大的质数
,为什么要比10^5大,是因为数据个数是10^5,最少要开10^5个位置,如果比10^5小,那么就放不下了,因为取模的结果一定比mod某个数的值小,选质数是因为质数可以保证冲突的情况最少,至于为什么,请移至百度(doge)- 为什么代码是这样
int k = (x % N + N) % N;
因为数据有可能是负数,而负数取模依然是负数,不满足要求,所以必须把数据映射成正数,这样做的目的就是映射成正数
找质数的代码
for (int i = 1000000; ; i++)
{
bool flag = true;
for (int j = 2; j * j <= i; j++)
if (i % j == 0)
{
flag = false;
break;
}
if (flag)
{
cout << i << endl;
break;
}
}
Q2:如何解决冲突?
- 由于映射过程中,可能出现
h[11] = 3, h[23] = 3
这样的情况,存在冲突,所以必须处理这种情况,有两种解决办法,分别是开放寻址法和拉链法
拉链法
开放寻址法
代码如下
拉链法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000003;
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;
return false;
}
int main()
{
int n;
scanf("%d", &n);
memset(h, -1, sizeof h);
while (n --)
{
char op[2];
int x;
scanf("%s%d", 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 = 2000003, null = 0x3f3f3f3f;
int h[N];
int find(int x)
{
int k = (x % N + N) % N;
while (h[k] != null && h[k] != x)
{
k++;
if (k == N) k = 0;
}
return k;
}
int main()
{
int n;
scanf("%d", &n);
memset(h, 0x3f, sizeof h);
while (n --)
{
char op[2];
int x;
scanf("%s%d", op, &x);
int k = find(x);
if (op[0] == 'I') h[k] = x;
else
{
if (h[k] == x) puts("Yes");
else puts("No");
}
}
return 0;
}