hash表

1.存储结构：
1.1开放寻址法
1.2 拉链法
2.字符串哈希

h(x)哈希函数
1.映射关系；
常见：mod
2.哈希冲突
冲突解决就是用1.开放寻址
2.拉链法，先建立一个hash数组，然后每个数组下面连接一条可以映射他的数组链表

例题：模拟散列数
1.向集合内插入一个数x
2.查询一个数
做法1：拉链法：

#include<iostream>
#include <cstring>

using namespace std;
const int N =100003;
int h[N];
int n[N];
int ne[N];
int in;

void insert(int x){
    int k=((x%N)+N)%N;
    n[in]=x;
    ne[in]=h[k];
    h[k]=in++;
    
}

int find(int x){
    int k=((x%N)+N)%N;
    for(int i=h[k];i!=-1;i=ne[i]){
        if(n[i]==x)return 1;
    }
    return 0;
}
int main(){
    char op[2];
    int x,n;
    cin>>n;
    memset(h,-1,sizeof h);
    while(n--){
        scanf("%s%d",op,&x);
        if(*op=='I'){
            insert(x);
        }
        else{
            if(find(x))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        } 
        
    }
}

做法2：开放寻址：
开放寻址的坑位要开到数据的两到三倍，防止陷入死循环

#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(){
    char op[2];
    int x,n;
    scanf("%d",&n);
    memset(h,0x3f,sizeof h);
    while(n--){
        scanf("%s%d",op,&x);
        int k=find(x);
        if(*op=='I'){
            h[k]=x;
        }
        else{
            if(h[k]!=null)puts("Yes");
            else puts("No");
        } 
        
    }
}