文章目录
基本思想：将一个大范围的数映射到小范围上
1、可以采用取模的方式，例如1~10 9 映射到 1~10 5，直接x
%100000即可。
2、取模冲突解决方式：拉链法、开放寻址法
(1) 拉链法：
开N个链表，N是比数据范围大的质数。
冲突的话在对应位置拉一条链，查找时沿着这条链查找
例如8%5=3，在3的位置放8；现在来了13，13%5=3，在3的位置拉一条链，链上填13。
int head[N], val[N], nxt[N], idx;
// 向哈希表中插入一个数
void insert(int x)
{
int k = (x % N + N) % N; // 保证余数为正
val[idx] = x;
nxt[idx] = head[k];
head[k] = idx ++ ;
}
// 在哈希表中查询某个数是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = head[k]; i != -1; i = nxt[i])
if (val[i] == x)
return true;
return false;
}
(2) 开放寻址法
只开一个数组，长度（映射范围）是数据范围的2~3倍的质数。
冲突的话去数组的下个位置，如果下个位置还有人，那再去下下个位置，直到没人为止。
查找也是一样，找不到就去下个位置找。如果某个位置没人且还没找到，那就是没有。
int h[N];
int null = 0x3f3f3f3f;
memset(h, 0x3f, sizeof h);
// 如果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;
}