模拟散列表

哈希表

存储结构：

开放寻址法

拉链法

字符串哈希方式

使用哈希表的情况：

1. 快速查找
2. 频率统计
3. 图的邻接表表示(在图的表示中，哈希表可以用来存储图的邻接表，快速访问某个节点的所有邻接节点。)
4. 把一个比较庞大的空间或者值域映射到一个较小的空间(把一个10^-9~10^9的数映射成0~10^5之间的数，完成这一过程的函数称为哈希函数

哈希函数写法：

1. x mod 10^5（mod的数尽量取质数）
2. 冲突（把不同的数映射成同一个数）

处理冲突的方法

开放寻址法

拉链法

拉链法

每一个位置都是一个槽，在每一个槽下面拉一条链，用来存储当前槽上已映射的数（槽代表的数字是链上映射成的数字）

AC代码

//拉链法
#include <cstring>
#include <iostream>using namespace std;const int N = 100003;int h[N], e[N], ne[N], idx;//h是槽，链用链表表示
//插入
void insert(int x)
{int k = (x % N + N) % N;//哈希函数+N再mod N目的是让K变成一个正数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;cin>>n;memset(h, -1, sizeof h);//把槽清空，空指针用-1表示while (n -- ){char op[2];int x;cin>>op>>x;if (*op == 'I') insert(x);//插入else{if (find(x)) puts("Yes");else puts("No");}}return 0;
}

开放寻址法

只开了一个一维数组，但是一维数组的长度经验上来说要开到题目上的2~3倍

AC代码：

//开放寻址法
#include <cstring>
#include <iostream>using namespace std;const int N = 200003, null = 0x3f3f3f3f;//Null表示这个位置是空的int h[N];//槽int find(int x)
{int t = (x % N + N) % N;while (h[t] != null && h[t] != x)//有人并且不是x{t ++ ;//往后继续看if (t == N) t = 0;//当看到最后一个位置，令t=0循环从第一个位置开始看}return t;//返回x在哈希表中的位置，如果x不在哈希表中则返回x应该存储的位置
}int main()
{memset(h, 0x3f, sizeof h);//把所有位置初始化为空int n;scanf("%d", &n);while (n -- ){char op[2];int x;cin>>op>>x;if (*op == 'I') h[find(x)] = x;else{if (h[find(x)] == null) puts("No");else puts("Yes");}}return 0;
}