题目描述

模板题：散列表的实现

C++代码

• 拉链法

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 3; //这里打表算出大于N的最小质数
// 拉链法
int idx, h[N], e[N], ne[N]; // e用来存储数据，ne是e中对应数据的上一个数据（指向h的），h用来存储idx记录是哪个e

void insert(int x){
    //c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
    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(){
    memset(h, -1, sizeof(h));
    int n, x;
    cin >> n;
    char op[2];
    while(n--){
        scanf("%s%d", op, &x);
        if(op[0] == 'I'){
            insert(x);
        }
        else{
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

• 开放寻址法

#include <iostream>
#include <cstring>
using namespace std;
//开放寻址法
const int N = 2e5 + 3; //开放寻址法一般都是开二倍的数组，同时找大于N的最小素数
const int null = 0x7f7f7f7f;//找一个大于x（10^9）的null进行初始化
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(){
    memset(h, 0x7f7f7f7f, sizeof(h)); //我估计是这个memset的原因，一旦写成0x7fffffff就不行了
    int n, x;
    cin >> n;
    char op[2];
    while(n--){
        scanf("%s%d", op, &x);
        int k = find(x);
        if(op[0] == 'I'){
            h[k] = x;
        }
        else{
            if(h[k] != null) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

memset解析

memset就是用一个字节进行按位初始化~

#include <iostream>
#include <cstring>
using namespace std;

int h[100];

int main(){
    memset(h, 0xffffff30, sizeof(h));
    for(int i = 0; i < 100; i++)
        cout << h[i] << " ";
    //memset(h, 0x3, sizeof(h));
    //输出结果：50529027 50529027 50529027 50529027 50529027 50529027 50529027 
    //换算成16进制为：0x3030303

    //memset(h, 0x7f, sizeof(h));
    //换算成16进制为：0x7f7f7f7f

    //memset(h, 0xffffff30, sizeof(h));
    //换算成16进制为：0x30303030

    //通过上述实验，得知memset就是用一个字节进行按位初始化~
}