将-10^9-10^9的数指向0-10^5的数 称为哈希函数
一般情况 x mod 10^5
但是这个简单方法可能将两个数映射到一个数而冲突

1.拉链法 如果两条链是冲突的 那么在同一位置用一个链将两个数都存下来
2.开放寻址法 (感觉这个简单一点)

[拉链法模拟散列表] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int N=100003; //模的数是质数且离2的n次方远 冲突概率最小
int h[N];//"给拉链开槽"
int e[N],ne[N],idx;

void insert(int x)
{
    int k= (x%N+N)%N; //c++里负数mod整数是负数 modN再+N再modN就是正的 k就是哈希值
    e[idx]=k; //先把新点值赋好
    ne[idx]=h[k]; //这一点的next指针指向槽里的下一个点
    h[k]=idx;//再让h[k]指向新点
    idx++;
    //插入操作 让新的点的next指针为h[k],让h[k]再指向这个新点
}

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;
        else return false;
}
int main()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof h); //清空
    while(n--)
    {
        char op[2];
        int x;
        cin>>op>>x;

        if(*op=='I') insert(x);
        else
        {
            if(find(x)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        } 
    }
}



开放寻址法不用开链表 但是一维数组开的长度要是题目的三倍
添加操作:先算k 从数组中第k个开始找 找到第一个空的就填
查找操作: 也是从第k位开始找 如果有数 对比是不是k 不是就找下一个 如果找到空就不存在
删除(不常用): 查找到后bool标记

[开放寻址法模拟散列表] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int N=200003; //需要开两到三倍
const int null=0x3f3f3f; //在数据之外的一个数 表示此位置无数
int h[N];
int e[N],ne[N],idx;

bool find(int x) 
{
    int k=(x%N+N)%N;
    
    while(h[k]!=null&&h[k]!=x) //如果这个位置有数 且不等于x 就下个位置
    {
        k++;
        if(k==N) k=0; //如果直到最后也没找到 从0开始循环
    }
    return k; //如果存在返回下标 不然返回应该存储的位置的下标
              //所以如果h[k]=null 那么就说明没有这个数


}
int main()
{
    int n;
    cin>>n;
    memset(h,0x3f,sizeof h); //全初始化为null
    while(n--)
    {
        char op[2];
        int x;
        cin>>op>>x;

        if(*op=='I') //插入
        {
            int k=find(x);
            h[k]=x;
        }
        else //查找
        {
            if(h[k]!=null) cout<<"Yes";
            else cout<<"No"; //如果h[k]是null  所以k不存在
        } 
    }
}