一、什么是散列表
又称哈希表，将一个比较大的值域映射到一个小的范围，比如0∼1000000000,映射到0∼100000范围内。原因是原来的值域是比较稀疏的，稠密的。
类似于离散化，离散化保序，而哈希表不保序。离散化是一种极其特殊的HashHash方式。
一般的操作有:
- 插入
- 查找
- 删除（算法竞赛一般不用）
下面我们来先看一道题目：
维护一个集合，支持如下几种操作： I x，插入一个数 x； Q x，询问数 x 是否在集合中出现过； 现在要进行 N 次操作，对于每个询问操作输出对应的结果。 输入格式 第一行包含整数 N，表示操作数量。 接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。 输出格式 对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。 每个结果占一行。 数据范围 1≤N≤105 −10^9≤x≤10^9 输入样例： 5 I 1 I 2 I 3 Q 2 Q 5 输出样例： Yes No
二、拉链法
#include <bits/stdc++.h>//C++万能头文件 using namespace std; const int N = 100003; //这个数字是根据FindGreaterPrime.cpp获取到的 //槽（坑） int h[N];//h[i]=x 表示键值为i的头结点指向的结点标号 //拉链法 int e[N]; //e[i]=x表示编号为i的结点对应的真实值 int ne[N]; //ne[i]=x表示编号为i的结点连接的子节点编号为x int idx; //结点符号 // 键值相同的元素构成一个单链表，h[i]是键值为i的单链表的头结点；insert函数采用的是头插法 //单链表插入 void insert(int x) { //如果x是负数，那么x%N就是一个负数，我们不想要一个负数，就加上一个N， //然后再模N就行了。 int k = (x % N + N) % N; //头插法 //1、添加一个新数据 //2、原来k的头接到新增加数据idx的后面 //3、把idx设置为k的头 //4、idx++方便下一次插入 e[idx] = x, ne[idx] = h[k], h[k] = idx++; } //查询操作 bool find(int x) { //同样的Hash函数 int k = (x % N + N) % N; //查找链表，看看有没有x for (int i = h[k]; i != -1; i = ne[i]) if (e[i] == x) return true; return false; } int main() { //优化输入 ios::sync_with_stdio(false); int n; cin >> n; //批量设置h数组内容为-1,清空槽，这是链表终点的初始值 memset(h, -1, sizeof h); while (n--) { string op; int x; cin >> op >> x; //插入x if (op == "I") insert(x); else { //检查是不是存在 if (find(x)) puts("Yes"); else puts("No"); } } return 0; }
三、开放寻址法
#include <bits/stdc++.h> using namespace std; //如果题目说是100000,那就需要找一个两倍大一点的质数（而且这个质数最好是靠近） //这个数字是根据FindGreaterPrime.cpp获取到的 const int N = 200003; //正无穷 const int INF = 0x3f3f3f3f; //因为题目的数据范围是1e9,而0x3f3f3f3f大于1e9，所以可以用来做特殊值判断 //开放寻址法 int h[N]; //核心操作 //找坑位：有两种方式会停止下来，一是找到了这个值，二是找到了坑位，用时再注意分辩 //如果存在，返回x存储的位置 //如果不存在，返回x应该存储的位置 //如果返回的位置上真实的值==x就是找到了，!=x就是找不到 int find(int x) { int k = (x % N + N) % N; while (h[k] != INF && h[k] != x) { k++; if (k == N) k = 0;//如果找到了最后一个位置，那么就回到0 } return k; } int main() { //输入优化 ios::sync_with_stdio(false); int n; cin >> n; //全部初始化为正无穷，判断是不是使用过此位置 memset(h, 0x3f, sizeof h); while (n--) { string op; int x; cin >> op >> x; int k = find(x); if (op == "I")h[k] = x; else { if (h[k] != INF) puts("Yes"); else puts("No"); } } return 0; }
