哈希表的概念

哈希表的定义 - 什么是哈希表?

哈希表 hash table, 又称散列表, 是根据关键字进行访问的数据结构

这里的关键字的意思就是要使用哈希表中存储的东西, 比如哈希表中存储着字母, 那么关键字就是字母(详细的例子就在后面)

• 哈希表建立了一种关键字和存储地址之间的映射关系, 这使得每个关键字与结构中的唯一存储位置相对应
• 在理想情况下, 在散列表中进行查找的时间复杂度为O(1), 即与表中的元素个数无关

其实我们在日常生活中已经不知不觉的使用过哈希表的思想了

案例: 统计一下字符串s = “abcabcc” 中, 每个字符的出现的次数, 字符串只包含小写字母

其实很简单, 我们创建一个大小为 26 的 cnt 数组, 因为只包含小写字母, 所以26就可以放下所有的字母, 我们假想这个 cnt 数组中的每个格子分别是 a 到 z 这 26 个字母. 而每个格子的数字大小就代表了这个字母出现的次数 然后遍历 s, 拿 s 中的每一个字母减去’a’ 得到一个位置 pos(其实就是 ascll 码值相减), 这个 pos 就是这个字母的位置, 最后我们将这个位置, 也就是这个字母出现的次数加一即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

string s = "abcabcc";
int cnt[26];

int main()
{
    for (auto ch : s) // 遍历 s, 记录字母出现的次数
    {
        cnt[ch - 'a']++;
    }

    for (int i = 0; i < 26; i++) // 打印 cnt 数组的值
    {
        printf("%c %d\n", 'a' + i, cnt[i]);
    }
    return 0;
}

其实这个 cnt 数组本质上就是一个哈希表, 在这里关键字就是小写字母; 映射关系就是 ch-‘a’; 存储位置就是cnt[ch-‘a’]

哈希函数

将关键字映射成对应的地址的函数就是哈希函数, 也叫做散列函数 记作: hash(key) = addr 比如上面提到的, ch-‘a’ 就是一个哈希函数, 记作: hash(key) = key - ‘a’

说白了, 哈希函数就是我们说的那个映射关系. 交给哈希函数一个关键字, 哈希函数就给我们计算出一个存储位置

所以说: 哈希表 = 用一个可计算的规则代替记忆,以少量冲突为代价,换来空间和时间的双赢 如果不好体会的话继续看下去下一个案例

哈希冲突

哈希函数可能会把两个或两个以上不同的关键字, 映射到同一个位置上, 这种情况被称为哈希冲突, 也叫做散列冲突. 起冲突的两个不同关键字叫做同义词

案例: 给定数组 a = {1, 3, 17, 1000000007, 49, 49, 1000000007}, 统计每个数出现的次数

关键字: 这里就是 1, 3, 17, 1000000007…. 这些数

思路 1: 直接创建一个 1e9+8 的数组把所有的数字都能放下, 那么哈希函数就是 hash(key) = key. 但是显然这是做不到的, 我们无法创建这么大的数组

思路 2: 因为我们的 a 数组有 7 个元素, 所以就算每个元素都不相同最坏 7 个格子就能存完, 于是我们创建大小为 7 的 cnt 数组 int cnt[7]; 那么 cnt 数组的下标范围就是 0~6 我们发现任意一个数 %7 之后的数就是在 0~6 之间, 于是我们的哈希函数是: hash(key) = key % 7, 这样我们就仅用大小为 7 的数组就解决了, 但是我们发现了一些问题

hash(1) = 1 % 7 = 1 hash(3) = 3 % 7 = 3 hash(17) = 17 % 7 = 3 hash(1000000007) = 1000000007 % 7 = 6 hash(49) = 49 % 7 = 0

我们发现关键字 3 和 17 指向了同一个存储位置 3; 此时两个不同的关键字放在了同一个位置上, 这便是发生了哈希冲突

提醒:

有些刚刚初学的人会认为, 反正我也就 5 种不同的数, 我直接创建一个大小为 5 的数组, 我脑子里面记到 下标 0 对应 1; 下标 1 对应 3; 下标 2 对应 17; 下标 3 对应 49; 下标 4 对应 1000000007;

这样不就好了吗? 但是你记到了不代表电脑记到了, 什么意思呢, 就是你如何去设计对应关系的问题

• 你人在计数的时候, 看到关键字 1, 哦, 他应该是在下标 0 的位置, 我把 cnt[0]++ 就行!看到关键字 17, 哦, 他应该是在下标 2 的位置, 我把 cnt[2]++ 就行!
• 但是计算机看到关键字 17 的时候他就蒙圈了, 我要把哪个存储位置++?因为计算机不记得这个约定

所以关键就是 “我心里记得”这件事,程序做不到

你脑子里的”1 放 0 号位,3 放 1 号位,17 放 2 号位……“本身就是一张对照表。程序要用它,就得把它存下来。存下来之后,下次拿到一个数 17,怎么知道它在 2 号位?只能从头翻这张表比对 – 这就是 O(N) 的遍历,和直接在原数组里线性查找没区别,哈希表就白做了

所以再来体会一句这句话: 哈希表 = 用一个可计算的规则代替记忆,以少量冲突为代价,换来空间和时间的双赢 相信现在你有更深的理解了

看到这里你可能会说:那是你 %7 取小了, 换个数不就行了?

很遗憾,不行。 在这个具体的案例中, 你可能把 %7 换成 %8或%9 就不会发生冲突了. 但是这只是个示例, 如果我把这几个数变动一下, 你还能保证%8 或 %9就不发生冲突了吗? 我们要探究的是任意出现的所有情况

哈希表表长 7, 而 int 的取值有 42 亿个, 按鸽巢原理, 必然有多个 key 落到同一个格子里。换成 % 13、% 10007, 乃至任何精妙的哈希函数,只要值域比表长大, 这个令人遗憾的结论就不会变。而想让表长追上值域,就退回到了思路1 的 1e9+8 数组. 更别说 key 是字符串时, 值域压根没法用下标

所以我们必须承认一个事实: 哈希冲突是不可避免的!

我们要做的不是消除它,而是:

1. 设计出优秀的哈希函数, 让 key 尽量散得均匀, 把冲突的概率降到最低;
2. 设计出合理的机制去处理冲突, 让它发生冲突之后哈希表依然能正确工作;

后面的内容,就围绕这两件事展开。>¬<

常见的哈希函数

直接定址法

在上面提到的第一个案例中: 统计字符串中小写字符出现的的次数使用的方法就是直接定址法.

直接取关键字的某个线性函数值为散列地址, 散列函数是 hash(key) = key 或 hash(key) = a * key + b 其中 a 与 b 为常数.

这种方式计算比较简单, 适合关键字的分布基本连续的情况, 但是若关键字分布不连续, 空位较多, 则会造成空间的浪费

除留余数法

上文的哈希冲突的案例就使用了除留余数法

除留余数法顾名思义, 假设哈希表的大小为 M, 那么通过 key 除以 M 的余数作为映射位置的下标, 也就是哈希函数为: hash(key) = key % M. 因此这种方法的重点就是选取适当的 M

建议 M 取不太接近 2 的整数次幂的一个质数. (具体原理可以参考算法导论里面的证明, 选取质数可以让分布更加均匀, 进而减少冲突)

除留余数法: hash(key) = key % N 但如果我这里的 key 是负数, 那么就会得到一个负数的结果, 但我们的下标必须是正数啊

于是我们需要一个key 是正数和负数都通吃的公式…

遇到负数, 比如 key 是-7, N 是5, -7 % 5 = -2. 然后我们加上 N, -2 + 5 = 3. 于是我们便得到了一个正数 3, 可以作为下标了! 这个公式就是 key % N + N 遇到正数, 比如 key 是7, 套用这个公式 7 % 5 + 5 = 7, 得到的是错误的结果. 难道我们还要写 if 来判断正负数吗?

其实再模回N就可以了, 也就是套用这个公式 (key % N + N) % N, 你会发现这个公式正负数都能用了, 这简称: 模加模

其他方法

上面两种方法是 <算法导论> 书籍中讲解的方法, 除此以外还有乘法散列法和全域散列法

其他书籍中还有一些巧妙的方法如: 平方取中法, 折叠法, 随机数法, 数学分析法等等, 这些方法相对更适用于一些局限的特定场景有兴趣的可以取研究研究

处理哈希冲突

有时候哈希表无论选择什么哈希函数都无法避免冲突

线性探测法

这里我们使用哈希表来存 a 这个数组, INF 表示无穷大, 我们使用线性探测的哈希表存数, 初始化哈希表的时候通常将表内的每个元素设定为无穷大. 一般 INF 是 0x 四个 3f. 即 INF = 0x3f3f3f3f;

如图我们计算出每个关键字的哈希值, 那么我们一个一个存入表中, 先存入 19, 应该在下标 8

然后我要存入 30, 也是在位置 8 与 19 的位置重叠了

根据线性探测: 依次向后进行探测直到没有存储数据的位置. 于是30 应该放在下标 9 这个位置 于是根据规律, 存完之后的整个哈希表应该是这样的 在之后如果反过来想要通过哈希函数计算出来的哈希值找到关键字在哈希表中的位置, 比如 hash(30) = 8, 于是我们首先找到下标 8, 发现不是 30, 按照线性探测, 我们依次向后寻找, 在下标 9 的位置找到了! 于是我们知道 30 存在下标 9 位置

线性探测的弊端

当哈希表中存的数比较密集的时候, 我可能要探测很多次才能找到我最终存下的位置, 那么想要 O(1)来查找或者存储每一个数就做不到了

比如上面的例子中, 我再要存一个关键字 8, 那么我要从下标 8 一直探测到下标 4 才能将这个关键字存下

对应线性探测, 通常的解决办法是创建一个合适大小的哈希表, 哈希表长 = 2 * a(存储数组的大小) => 在附近找到一个质数. 比如上例中 a 大小为 8, 那么我就创建一个大小为 16 的哈希表, 但是要是质数, 所以我们创建大小为 17 即可. 于是哈希函数的模数就可以选择 %17

链地址法

在使用链地址法的时候哈希表每个元素初始化为 0, 0 代表指针为空并没有指向任何一个数

根据计算出的结果将关键字挂在这个哈希表上 ### 链地址法的弊端

如果冲突特别多, 比如哈希值全部都是 8, 那么所有的数就会在 8 下面形成一个链表, 这样查找或插入的时候时间复杂度就变成了O(n)

解决方法是: 如果在某一个点的冲突特别多, 我们就不使用链表, 而是使用红黑树来将冲突的关键字串起来, 这样时间复杂度从 O(n) 降低到 log(n)

哈希表的模拟实现

这里我们试试不用 STL, 而是自己去实现一个模拟的哈希表 ## 案例:模拟散列表

维护一个数据结构,初始时为空。请支持下面的操作:

现有 n 次操作,针对每次查询,输出 x 是否在该数据结构中

输入描述

第一行一个整数 n,表示操作次数。

之后 n 行,第 i 行两个整数 op、x,分别表示第 i 个操作的类型 op,以及元素 x。

输出描述

对每个 2 x 操作,输出查询结果

测试用例

输入

1
2
3
4
5
6
7
8
9
10
11
12
13

12
1 1
1 2
1 3
1 4
1 5
2 2
1 6
2 5
1 7
2 8
2 4
2 10

输出

1
2
3
4
5

Yes
Yes
No
Yes
No

线性探测法

根据样例, 这里最多要存 7 个数, 那么哈希表长应为 17 较好

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
49
50
51
52
53
54
55
56
57
58
59
60
61

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

const int N = 17, INF = 0x3f3f3f3f;
int h[N]; // 创建哈希表


void init() // 初始化哈希表的函数
{
    memset(h, 0x3f, sizeof(h));
}

int f(int x) // 确定 x 位置的哈希函数
{
    int pos = (x % N + N) % N;
    while (h[pos] != INF && h[pos] != x)
    {
        pos++;
        if (pos == N)
            pos = 0;
    }
    return pos;
}

void insert(int n) // 插入函数
{
    int pos = f(n);
    h[pos] = n;
}

void find(int n) // 查找函数
{
    int pos = f(n);
    if (h[pos] == n)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

int main()
{
    init();

    int m = 0;
    cin >> m;
    while (m--)
    {
        int op, x;
        cin >> op >> x;
        if (op == 1)
        {
            insert(x);
        }
        else
            find(x);
    }

    return 0;
}

链地址法

代码实现上和树的链式前向星一模一样

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
49
50
51
52
53
54
55

#include <iostream>
using namespace std;

const int N = 17;
int h[N], e[N], ne[N], id;

int f(int x)
{
    int pos;
    pos = (x % N + N) % N;
    return pos;
}

void insert(int n)
{
    int pos = f(n);
    id++;

    e[id] = n;
    ne[id] = h[pos];
    h[pos] = id;
}

void find(int n)
{
    int pos = f(n);
    for (int i = h[pos]; i; i = ne[i])
    {
        if (e[i] == n)
        {
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
    return;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int op, x;
        cin >> op >> x;
        if (op == 1)
        {
            insert(x);
        }
        else
            find(x);
    }
    return 0;
}

STL中提供的哈希表

unordered_set 和 unordered_multiset

set 与 unordered_set 唯一的区别就是前者使用红黑树实现, 后者使用哈希表实现. 使用的方式完全一样. 无非就是存储和查找的效率不一样, 已经前者是有序的, 后者无序

unordered_map 和 unordered_multimap

和 map 的使用也是一样的, 通过 map 可以存放键值对, 这样我们就能顺利的存下一张图了

比如这里我们用邻接表的方式存一张无向图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

unordered_map<int, vector<int>> edges;
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int a, b;
        cin >> a >> b;
        
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    return 0;
}