哈希表相关知识

 840. 模拟散列表

1、拉链法

要点1：const int N 最好是比100000大的第一个质数

求质数的代码:

int main(){
    for(int i=100000;;i++){
        bool flag=true;
        for(int j=2;j*j<=i;j++){
            if(i%j==0){
                flag=false;
                break;
            }
        }    
        if(flag){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}

拉链法

//拉链法
#include <bits/stdc++.h>
using namespace std;

const int N=100003;

int h[N],e[N],ne[N],idx;

void insert(int x){
    int k=(x%N+N)%N;//k为哈希值
    //在c++中，负数的模为负数，加N后肯定为正数
    e[idx]=x;
    ne[idx]=h[k];//新节点的next指向h[k]
    h[k]=idx++;//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;
        }
    }
    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);//scanf读字符串可以自动把空格回车制表符忽略掉，就可以降低出错的概率
        //但是一般不用scanf读字符
        if(*op=='I')insert(x);
        else{
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
}