一、什么是散列表？
散列表又叫哈希表，通俗来讲，就是把范围很大的一个数组中的数映射到范围很小的数组中去。比如说把1000范围的数映射到100范围中。那么问题来了，如果真的有1000个数需要映射到大小为100的数组中，那么就一定有两个或两个以上的数映射到数组中的同一个位置，好比我们去蹲坑，1000个人，但是只有100个坑，不可能每个人都有一个坑，至少有两个人会在同一个坑里拉这自然是不行的，我们把这种情况叫做冲突，所以我们需要解决冲突，下面我们详细讲解两种解决冲突的方式，分别是拉链法和开放寻址法。
二、散列表的两个基本操作
插入操作
查找操作
这两种操作在不同的方法中会有不同的实现，如下：
三、拉链法
先看一幅图：
1.基本原理
把一个范围很大的数组映射在上面的数组当中，如果有两个或两个以上的数据被映射到同一个数组元素中，那么就采用单链表来存储，每一个数组单位都有一个链表且是该链表的表头，这就是基本的存储结构。
2.插入操作
首先找到旧数组在新数组中的映射，也就是某一个数组元素，然后按照链表的方式插入
void insert(int x)
{
int k = (x % N + N ) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
}
3.查找操作
首先也是先找到某一个数在新数组中的映射，也就是一个数组元素，然后以这个数组元素为链表的表头，遍历该链表，如果找到就返回true，如果没找到就返回false
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;
}
4.案例
维护一个集合，支持如下几种操作：
I x，插入一个数 x；Q x，询问数 x 是否在集合中出现过；
现在要进行 N 次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N，表示操作数量。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。
输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤N≤105 −109≤x≤109
输入样例：
5
I 1
I 2
I 3
Q 2
Q 5
输出样例：
Yes
No
代码如下：
#include <iostream>
#include <cstring>
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;
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 == 'I') insert(x);
else
{
if(find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
四、开放寻址法
1.基本原理
把一个范围很大的数组映射到一个新数组当中。把某一个元素映射到新数组中的某个位置时，如果该位置为空（或为无穷大），就把那个元素放在这个位置，如果该位置不为空（其实就是之前已经放了一个元素了），就把这个元素放在该位置的下一个位置，如果下一个位置也不为空，就把这个放在再下一个位置，以此类推，查找插入都是这个过程。
其实主要就是查找操作，插入操作就是在查找操作的基础上进行了赋值。
2.查找操作
查找某一个元素x，如果映射到新数组的位置上为空，就返回该位置
如果映射到新数组的位置上不为空，且该位置存放的元素为x，就返回这个位置
如果映射到新数组的位置上不为空，且该位置存放的元素不为x，则位置++，直至某一个位置为空或者为空且值相同
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;
}
3.插入操作
要插入某一个元素x，先映射到新数组，再查找有没有这个x
如果恰好有的话，就重新赋值为x，其实都一样，存放的还是x（其实不修改也行，但是这样做方便书写下面的代码（两行搞定），否则还得再写一个if语句）
如果没有，就找到从映射到的位置之后为空的那个位置，把这个x放进去
int k = find(x);
h[k] = x;
4.案例
还是拉链法中的例子，这次用开放寻址法重新解决
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003, 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);
if(*op == 'I')
{
int k = find(x);
h[k] = x;
}
else
{
int k = find(x);
if(h[k] != null)
puts("Yes");
else
puts("No");
}
}
}
