【STL 源码剖析】系列十三：关联式容器 --unordered-set、unordered-map、unordered-multiset 和 unordered-multimap

前言

在了解 hashtable 之后，下面就可学习基于 hashtable 的 set 和 map。在之前的介绍中，我们直到 set 和 map 主要是为了提升查找效率，所以采用红黑树的底层机制，查找效率可以达到 O (logn)。但是这是基于元素的随机性。

而对于 hashtable 而言，不需要基于元素的随机性假设就可以使得元素的存取和删除达到常数级。

本篇主要是介绍基于 hashtable 实现的 set、map、multiset 和 multimap。虽然这里介绍时采用的是 C++11 标准之前的 hash_set、hash_map、hash_multiset 和 hash_multimap，但是设计思想是一致的，只是在一些接口上有些许差别。

本篇主要内容：

1. 基于 hashtable 实现的 set 和 map；

2. 基于 hashtable 实现的 multiset 和 multimap。

注：基于 hashtable 实现的 set 和 map 对外接口在 hashtable 几乎以及实现，因此只需要调用即可，实现细节参考 hashtable。本篇基本只是代码注释和简介，会比较枯燥。

hash_set (C++11 中的 unordered_set)

之前介绍的 set 底层实现是 RB-Tree（红黑树），但是 SGI 提供了另一种以 hashtable 作为底层机制的 set（C++11 标准中是 unordered_set）

使用 set 的目的是快速查找元素，这一点不管是红黑树还是哈希表都能完成。但是底层实现是红黑树的 set 实际上是有序的，而底层实现是哈希表的 set 是无序的 (注意，如果插入元素小于哈希表大小，那么可能会造成有序的假象)。

hash_set 所有对外接口都由 hashtable 提供，所以 hash_set 的所有行为都是调用哈希表的行为。

注意 set 的元素键值就是实值，hash_set 与 set 的使用方式完全相同。

下面是 hasn_set 的源代码摘录：

hash_map (C++11 中的 unorder_map)

与 set 一样，map 也可以使用 hashtable 作为底层实现机制，表示为 hash_map，使用与 map 完全一样。

hash_map 内部元素同样是无序的。

下面是源代码摘录：

hash_multiset (C++11 中的 unordered_multiset)

hash_multiset 特性与 multiset 完全相同，唯一的区别就是底层实现是 hashtable。

hash_multiset 实现上与 hash_set 的唯一区别就是：前者的插入操作使用底层机制 hashtable 的 insert_equal，而后者采用 insert_unique。

因此这里不再列举源代码。

hash_multimap (C++11 中的 unordered_map)

hash_multimap 特性与 multimap 完全相同，唯一的区别就是底层实现是 hashtable。

hash_multimap 实现上与 hash_map 的唯一区别就是：前者的插入操作使用底层机制 hashtable 的 insert_equal，而后者采用 insert_unique。

因此这里不再列举源代码。