哈希表（c++）

1、介绍

哈希表，也称为散列表，是一种非常高效的数据结构。它通过将键（Key）映射到数组的特定位置来快速查找、插入和删除数据。这个映射过程由哈希函数（Hash Function）完成，该函数将键转化为一个整数，该整数用作数组的下标。

2、实现

哈希表将一个很大的集合映射成0~N
例如： 将x属于（-10^9 ~ 10^9）映射到0~10^5里
两部操作首先： x mod 10^5;
       其次 ： 解决冲突{
          两种办法：{
            拉链发 和 开放寻址法
          }
       }

上述需要注意在做模运算的时候，最好取比10^5第一个大的质数模，这样会减少冲突，冲突指的是会映射到一个地方去

2.1、拉链法

图解：

注意：算法题里，一般只会考添加和查找，几乎很少考删除操作，就算考删除，也不会真的删除，只是跳过这个点

添加操作和查找操作类似于单链表

如图：

2.2、开放寻址法

此方法只需要一个一维数组就可以实现

• 规则：

• 空间开到2~3倍的N：目的是可以减少冲突

• 这里同样要找到开的N的第一个质数

3、例题：840. 模拟散列表 - AcWing题库

拉链法：

#include<iostream>
#include<cstring>

using namespace std;
//找到100000的第一个质数去mod会减少冲突
const int N = 100003;
//h[]表示映射数组，e[],ne[]是单链表e存数，ne指向下一个节点,idx分配空间
int h[N],e[N],ne[N],idx;
//拉链法的存入操作
void insert(int x)
{
    //先让x%N是为了避免负数很大的情况，不能先加N再mod。
    int k = (x % N + N) % N; 
    e[idx] = x;//存入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[0] == 'I')
        {
            insert(x);
        }
        else
        {
            if(find(x)) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

开放寻址法：

#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;//寻找映射值
    //去寻找k的位置，如果k下有这个数返回的就是这个数的位置
    //如果k下没这个数，返回的是这个数应该存的位置
    while(h[k] != null && h[k] != x)
    {
        k++;
        if(k==N) k = 0;
    }
    return k;
}

int main()
{
    int n;
    scanf("%d", &n);
    //解释一下这里为啥是0x3f是因为memset是按字节去存储的，一个int是4个字节
    //每个字节是0x3f所以4个字节就是3f3f3f3f
    memset(h,0x3f,sizeof h);
    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s %d", op, &x);
        int k = find(x);//与拉链法区别是，寻址法都需要寻找k，直接合并成一个就可以
        if(op[0] == 'I')
        {
            h[k] = x;
        }
        else
        {
            if(h[k] == x) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}