模拟散列表

模拟散列表概述

散列表又称哈希表，它是通过哈希函数来将一个关键字映射到另一个关键字，来实现快速增删改查的数据结构，增删改查的时间复杂度近乎$O(1)$

散列函数

哈希函数，我们也用的是简单的一种，对$N$取模，$N$为质数时候，冲突的可能性会更小

哈希表根据解决冲突的办法，我们可以得出来两种方案

开放寻址法

我们需要想到一个解决冲突的办法，如果冲突，我们就需要再散列，也就是找到下一个位置，这时我们可以挨着找下一个位置，也可以每隔几个选择下一个位置，这些都是线性探测再散列。同样，也可以通过平方探测再散列，双散列等方法找到下一个位置

数据存储问题

我们这里就采用最简单的处理方法，从当前位置往下走，哪个位置可用，就用哪个位置

开放寻址法的数组空间开辟是数据量的两倍到三倍，综合考虑时间空间这样是最好的

分离连接法

我们这里开了跟数据规模等大的链表数组，如果散列到一个位置，我们就把当前数字插入到对应位置的列表

查找时候就查找对应链表即可

思路分析

开放寻址法

这里$find$函数的功能是
$(1)$ 数字存在，就返回查找数字的位置
$(2)$ 数字不存在，就返回该数字应该放到的地方

这里需要注意，如果遍历完整个数组，我们需要从头接着遍历，由于数组开的规模是数据规模的两倍以上，所以不会出现死循环问题

处理插入操作，就用$find()$函数找到应该放的位置，将数据填入
处理查找操作，就用$find()$找到位置，看看那个位置上的数据是不是我们需要的输出

初始化的问题

我们需要定义一个数据（空指针）表示该位置上没有数，由题意得，在正负$1e9$外即可，那么可以赋值为$0x3f3f3f3f$

赋值语句

    memset(h, 0x3f, sizeof h);

分离链接法

插入，就在对应链表内插入

查找就是遍历链表

这里链表写法和之前讲过的一致

代码

开放寻址法

#include <cstring>
#include <iostream>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f; // 定义数组规模，与空指针

int h[N];

int find(int x) // 该数据存在，返回该数据位置；不存在就返回应该插入的位置
{
    int t = (x % N + N) % N; // 确保映射后的范围在数组容纳范围内
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0; // 遍历到尾，就接着从头遍历
    }
    return t;
}

int main()
{
    memset(h, 0x3f, sizeof h);

    int n;
    scanf("%d", &n);

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}

分离链接法

#include <cstring>
#include <iostream>

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;
    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;
}