模拟散列表

发表于 更新于 分类于 Artalk： loading...
hashtable 模拟散列表 哈希表

前言

散列表，又称哈希表（Hash table），相关知识已经很熟悉，不再赘述，备忘参考哈希表_百度百科

重心放在代码实现上

image-20211126141822071

其实个人认为y总讲的所谓的存储结构就是解决冲突的方式，一般常用的是开放定址法和拉链法，开放定址法中又分为线性探测、再散列等。

有点类似离散化，将一个大范围内的数（[−109∼109][-10^9 \sim 10^9]），通过散列函数h(x)h(x)，映射到一个较小范围上（h(x)∈(0,105)h(x)\in(0,10^5)）。但是离散化是需要保序的，哈希是无序的。

yxc：离散化是极其特殊的哈希方式。

模拟散列表-acwing 840

算法思路

课程中默认的散列方法是除留余数法

EX:h(x)=x mod QEX: h(x)=x \bmod Q

注意：一般Q取一个质数，并且距离2的整数次幂尽量远。

这样发生冲突的概率小

参照知乎问题-Hash时取模一定要模质数吗

QQ取10510^5，即x mod 105,∈(0,105)x \bmod 10^5, \in(0, 10^5)

解决冲突的方法：

拉链法

期望算法，每个链表的长度都可以认为很小，整体的查询速度近乎O(1)O(1)

image-20211126144632250

插入时，如果发生冲突，就将冲突的关键词挂到这个位置的同义词链表上。

例如上图，11和23都映射到了3这个位置，发生冲突，11和23就是”同义词“。

1
2
3
4
5
6
7
void insert(int x) {
    int k = (x % N + N) % N; // 加N目的是让余数变成正数
    e[idx] = x;
    ne[idx] = h[k]; // h[k]相当于head头指针
    h[k] = idx; // 头插法
    idx ++;
}

查询时，先将x通过散列函数映射到散列表的对应位置k上，然后遍历位置k对应的链表，检查是否存在关键字x

1
2
3
4
5
6
7
bool find(int x) {
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i]) { // h[]存的是一个个链表节点的“地址”
        if (e[i] == x) return true;
    }
    return false;
}

删除元素比较复杂，真正实现的时候，也不会真的删除。一般会额外创建一个布尔数组来保存每个节点的状态，进行标记。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstring>
#include <iostream>

using namespace std;

const int N = 100003; // 这里的N是经过计算的大于1e5的第一个质数

int h[N]; // 散列表 
int e[N]; // 链表
int ne[N], idx;

void insert(int x) {
    int k = (x % N + N) % N; // 加N目的是让余数变成正数
    e[idx] = x;
    ne[idx] = h[k]; // h[k]相当于head头指针
    h[k] = idx; // 头插法
    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)); // 先将散列表清空，空指针的“地址”为-1
    while (n -- ) {
        char op[2];
        int x;
        // 用scanf读的时候尽量用字符数组
        // 这样scanf会自动忽略掉回车、空格、指标符，降低出错的概率
        scanf("%s%d", op, &x);
        
        if (*op == 'I') insert(x);
        else {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

关于以上代码

  1. 用 scanf读取字符串的时候尽量用字符数组，这样scanf会自动忽略掉回车、空格、指标符，降低出错的概率，例如

    1
    2
    char op[2];
    scanf("%s", op);

  2. int k = (x % N + N) % N;加NN的目的是让所有的余数都为正数。

    例如：在c++中，负数取模相当于，先取绝对值，再取模，最后结果加个负号。

    -10 % 3 = -1

后续的图论中，存点vertex的时候同拉链法类似——邻接表

开放定址法

yxc：我用的比较多的是开放定址法。

基本思想，一个散列表项，既向其同义词开放，又向其异义词开放。

这里默认的是开放定址法中的线性探测法。

image-20211126155501385

开放定址法只需维护一个h(x)h(x)数组即可，一般来说，数组长度是数据范围的两到三倍。

删除时，同样的，查找到x时，不会真的删除，而是在数组中打一个标记。

核心：find函数

与拉链法略微不同，这里的find函数，如果x存在的话，返回的是x存储的位置，如果不存在的话，返回的是x应该存储的位置。

1
2
3
4
5
6
7
8
9
10
const int null = 0x3f3f3f; // 定义一个大于10^9（超出数据范围）的数，为散列表项为空的标志
memset(h, null, sizeof(h));
int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x) { // 当前散列表项不为空，且不等于x
        k ++; // 向后寻找空位
        if (k == N) k = 0; // 寻到末尾的话，从头开始
    }
    return k;
}

插入的话直接令h[find[x]] = x即可。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstring>
#include <iostream>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];

int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x) { // 当前散列表项不为空，且不等于x
        k ++; // 向后寻找空位
        if (k == N) k = 0; // 寻到末尾的话，从头开始
    }
    return k;
}

int main() {
    memset(h, null, 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;
}