基于哈希的 map 和 set

简述

基于哈希的 map 和 set ，它们分别叫做 unordered_map, unordered_set 。数据分布越平均，性能相较 map 和 set 来说提升就更大。但由于它们基于哈希，所以并不像 map 和 set 一样能自动排序；它们都是无序的。

我做了一个测试：随机生成 $10^7$ 个 int 范围内的整数（平均分布），然后将其分别插入 map 和 unordered_map，再完整的做一次查询，查看时间和内存上的消耗。

测试结果

当数据分布平均时，从时间上看，两者的性能差距约为 $7138 / 18041 \approx 40\%$

请注意random库与chrono库均是C++11。

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

#include <chrono>
#include <iostream>
#include <random>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

// 生成 [a, b] 范围内的整数
// 其中 INT_MIN <= a <= b <= INT_MAX
int rand(int a, int b) {
    static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<int>(a, b)(rng);
}

// 生成 [a, b] 范围内的整数
// 其中 0 <= a <= b <= UNSIGNED_INT_MAX
unsigned rand(unsigned a, unsigned b) {
    static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<unsigned>(a, b)(rng);
}

// 生成 [a, b] 范围内的整数
// 其中 LONG_LONG_MIN <= a <= b <= LONG_LONG_MAX
LL rand(LL a, LL b) {
    static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<LL>(a, b)(rng);
}

// 生成 [a, b] 范围内的整数
// 其中 0 <= a <= b <= UNSIGNED_LONG_LONG_MAX
ULL rand(ULL a, ULL b) {
    static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<ULL>(a, b)(rng);
}

int main() {
    const LL MAX = 1e10;
    cout << rand(-MAX, MAX);
    return 0;
}

传送门

此题让我们实现一个LRU的模板类。本题较简便且高效的写法是维护一个std::list和一个std::unordered_map。

std::list 与 std::unordered_map 中存放的内容

std::list中存放各key，类型为K。链表中各键码存放的顺序是按照访问顺序存放的。

std::unordered_map中以key为第一维，第二维为一个pair，其first和second分别为：

first: 该key对应的value。

second:该key在std::list中的迭代器方便访问。

为方便，下面用“链表”来指代std::list，用“哈希表”来指代std::unordered_map。

各操作实现

insert操作：用哈希表判断该键是否已经存在。若存在，先在链表中删除该key，然后再新加一个该key到链表尾部，并更新在哈希表中的value和链表的迭代器。若不存在，则直接加至链表尾部，并在哈希表中插入该key，伴随着对应的value和链表迭代器。

get操作：直接从哈希表中获得其value即可。代码实现未检测该key是否存在，严谨来说应该加上异常处理。

contains操作：直接在哈希表中查询是否存在该key即可。

vis操作：用哈希表判断该键是否存在。若不存在，则本操作无效。否则，将该键从链表中删除，然后再将其加至链表尾部，并更新哈希表中对应链表迭代器。

pop操作：判断是否整个容器已经为空。若为空，则本操作无效。否则，将链表头部元素从链表中删除，并在哈希表中删除对应键值信息。

remove操作：用哈希表判断该键是否存在。若不存在，则本操作无效。否则，将该键从链表中删除，并在哈希表中删除对应键值信息。

empty操作：哈希表或链表判空即可。

size操作：取哈希表或链表大小即可。

clear操作：清空哈希表和链表即可。

时间复杂度

各操作基于对链表和哈希表的修改。期望复杂度均为$O(1)$。