模拟散列表
把一个较大范围内的数转化为较小范围的数的集合。
模上一个数(x%N+N)%N防止下标出现负数
数据结构
用一个数组表示要插入的槽，如果哈希产生了冲突，则把数插入到槽中(单链表)。
数组+模拟链表
拉链法
实现代码：
#include<cstring>
#include<iostream>
using namespace std;
const int N = 100003; // 最好选质数
int h[N],e[N],ne[N],idx;
// 把某个数插入到槽内
void insert(int x)
{
int k = (x%N+N) % N; // 求槽的下标
e[idx] = x; // e数组是存取插入所有数的数据
ne[idx] = h[k]; // 开始终点为-1，指向上一个结点,记录单链表
// 的上一个结点
h[k] = idx++; // 结点递增
}
// 散列表查询
bool find(int x)
{
// 找到所在的槽
int k = (x%N+N)%N;
for(int = h[k];i != -1;i=ne[i])
{
if(e[i] == x) return true;
}
return false;
}
int main()
{
// 先把每个槽都置为-1，因为没有上个结点存在
memset(h,-1,sizeof h);
}
开放寻址法
在一个数组中存数，如果当前位置没有人，则可以插入；否则一直向后查找，直到找到一个空位进行插入。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 200003, nul = 0x3f3f3f3f;
// N 应该为数据总数的整数倍数
int h[N];
int find(int x) // 查找和插入通用的函数
{
int k = (x%N+N)%N;// 先锁定下标,再找空位
while(h[k] != nul && h[k]!=x)
{
k++;
if(k==N) k = 0; // 到尾了，返回头部进行插入
}
return k;
}
int main()
{
memset(h,0x3f,sizeof h);
int x;
cin >> x;
int k = find(x);
// 插入
h[k] = x; // 找到可以插入的空位
// 查询
if(h[k] != nul) puts("存在该数字");
// 如果当前的位置为空位，说明之前这个数字并没有进行插入，所以没有出现过
}