数据结构与算法学习笔记----哈希表

数据结构与算法学习笔记----哈希表

@@ author: 明月清了个风

@@ first publish time: 2024.12.3

哈希表（Hash Map）

哈希表是一种基于数组的数据结构，通过哈希函数将值映射到数组的索引位置，从而实现高效的数据存储和检索。

哈希的基本操作包括插入(insert)、查找(search)和删除(delete)，其平均时间复杂度为$O(1)$。

实现原理

1. 哈希函数：哈希函数将元素转换为数组的索引进行存储，对于不同的元素应有不同的输出，减少碰撞概率，使元素能够均匀的分布到哈希表中的不同位置。
2. 碰撞处理：哈希表无法完全避免碰撞， 当出现碰撞时主要的有两种方法
   • 链式法（y总说的拉链法）：每个哈希表的槽都是一个链表（同样用数组模拟），当多个元素映射到同一槽位时，哈希表通过邻接表进行存储。
   • 开放寻址法：发生碰撞时，哈希表通过一定的寻址策略，如线性探查、二次探查寻找下一个空闲槽位进行存储。
3. 动态扩容：当哈希表存储元素过多后（负载因子进行衡量，负载因子 = 元素数量 / 表的容量），哈希表进行动态扩容。

特点

1. 操作效率高，一般情况下，查找、插入、删除的时间复杂度都可以看做$O(1)$。
2. 空间占用：哈希表对于空间的要求较高，预留较大的空间同样可以减少碰撞，空间换时间。
3. 不保序：哈希表中的元素存储不能保证数据之间的顺序，这是与之前讲过的离散化的区别

拉链法

拉链法通过链表对所有的哈希键值进行存储，如图所示。

首先讲一下邻接表的构建方式，代码如下

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

void init()
{
    memest(h, -1, sizeof h);  // 所有表头初始化为-1
}

void insert(int x)
{
    int k = hash_func(x);
    e[idx] = x, ne[idx] = h[k], h[k] = idx ++;
}

bool find(int x)
{
    int k = hash_func(x);
    for(int i = h[k]; i != -1; i = ne[i])
    {
        if(e[i] == x) return true;
    }
    return false;
}

对于每个$a_x$值，通过唯一的哈希函数$hash-func$进行映射得到在哈希表中的键值$k$，意味着邻接表中$key$值为$k$的地方存储$a_x$。

• h[k]表示哈希值为k的元素最后所在的链表表头，其中存储的是元素的编号idx，如图中所示，目前哈希值$key$为0的h[0]表头为idx为4的元素，也就是h[0] = 4，其所在链表的元素编号分别为4 3 1 -1，其中-1是标志位，表示链表结束。

• e[idx]存储编号为idx的元素的值，如图所示，e[0]存储的是哈希值$key$为1，编号idx为2的元素，简单来说对于每一个要存的数$a_x$，都有三个数一一对应：元素值$a_x$，哈希值$k$，存储编号$idx$。

• ne[idx]存储编号为idx的元素所在链表的下一个元素的编号，如图所示，存储在h[0]的编号为4的元素的下一个元素为3，也就是ne[4] = 3。

⭐️单链表插入的模拟过程讲解

这里邻接表使用的是头插法，新元素入队插入队头，如图中红色虚线框所示：

假设现在计算得到的$key$值为$10$，那么就要在哈希表索引为$10$的链表上插入这个元素。

红色虚线框中左边为插入前的情况，目前哈希值$key$为10的地方存的元素编号idx为9，且以他为表头的链表中只有他一个元素。

现在要插入编号idx为10的元素，就要使用上面代码中的insert函数。

首先根据要插入的数的值$a_x$计算得到哈希值为10，因此要插入到h[10]中。

然后要进行三步e[idx] = x, ne[idx] = h[k], h[k] = idx ++;

因为这是第10个插入的数（正好和$key$值相同了哈哈，注意区分），因此e[10] = a_x；然后因为是头插法，所以将原来的表头h[10] = 9赋值给[ne[10]]，也就是ne[10] = h[10]，注意这里的两个10的含义不同，最后将新插入的编号idx为$10$的元素作为新的表头h[10] = 10。

⭐️哈希函数

这里使用的是模运算哈希，为了减少碰撞，应尽量选择一个质数，这里y总说有数学证明，但是我没去看过，就不说了，以后再补吧。由于C++中的模运算会有负数，因此对于负数的模运算要进行以下的操作保证得到的哈希值为正数k = (x % N + N) % N.

开放寻址法

相较于链式法，开放寻址法相对会更节省一点空间，只需要开一个哈希数组h[N],容量为预计要存的元素的$2\sim 3$倍即可，所有的元素都直接存在哈希表中，不像链式法，哈希表中存储的是哈希值相同的元素的链表头。

当出现碰撞时，继续遍历哈希表找到下一个空闲位即可，核心代码如下

const int null = 0x3f3f3f3f; 

int h[N];  // 容量开2-3倍

void init()
{
    memset(h, 0x3f, sizeof h);  // 所有位置初始化成一个不可能的数。
}

int find(int x)
{
    int t = (x % N + N) % N;    // 求哈希值
    while(h[t] != null && h[t] != x)    // 如果对应位置存了其他的数，找下一个位置t++
    {
        t ++;
        if(t == N) t = 0;     // 越界了就从头开始找。
    }
    return t;
}

Acwing 840. 模拟散列表

[原题链接](840. 模拟散列表 - AcWing题库)

维护一个集合，支持如下几种操作：

1. I x，插入一个整数$x$；
2. Q x,询问整数$x$是否在集合中出现过；

现在进行$N$次操作，对于每个询问操作输出对应的结果

输入格式

第一行输入整数$N$

接下来$N$行，每行包含一个操作指令。

输出格式

对于每个询问指令Q x，输出一个询问结果，如果$x$在集合中出现过，则输出Yes，否则输出No.

数据范围

$1\le N\le 10^5$,

$1\le x\le 10^9$

代码—链式法

#include <iostream>
#include <cstring>

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

代码—开放寻址法(直接搬的y总的)

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