引言

unordered_map是我接触的第一个哈希容器，之前只知道它“查得快”，对bucket、负载因子这些概念完全没有概念，更不知道map中的键竟然有专门的修改方式。

于是我写了一个unordered_map方法的示例实验，从插入访问到bucket结构逐个观察。

在此篇文章中，我将记录下自己对unordered_map的理解，重点放在它与其他容器不同的哈希结构上，以供思考，如有不足之处欢迎指正。

正文

与其他容器共通的部分

共通的部分简要一提：empty()/size()、clear()这类容量与状态方法自不必说，insert()配合迭代器的用法也与vector同源，erase()同样接受key或迭代器，返回下一个位置的迭代器，迭代器失效的规则在前面的实验里已经记录过。

插入与访问

插入有三种常见写法：

unordered_map<string, int> map;
map["apple"] = 1;//operator[]，key不存在时先插入再赋值
map.insert({"banana", 2});//列表构造pair插入
std::pair<string, int> pair{"orange", 3};
map.insert(pair);//显式pair插入

[]与insert()的语义差异值得注意：operator[]在key不存在时会先创建一个默认值再返回引用，而insert()在key已存在时什么都不做。 所以“查询”场景应该用contains()或find()，避免[]无意中插入新元素。

if (map.contains("apple"))//c++20
    cout << map.count("apple") << endl;//实际上map不允许重复，count取值只有0或1

count()只有0和1两种取值，这也算是map类容器“键唯一”的一个佐证。

哈希结构：bucket与负载因子

unordered_map的底层是哈希表，实验里直接把内部结构打印了出来：

cout << map.bucket_count() << endl;//桶的数量
cout << map.load_factor() << endl; //负载因子：size / bucket_count
cout << map.max_load_factor() << endl;//负载因子上限，超过则自动rehash
cout << map.bucket("banana") << endl;//banana落在哪个桶
cout << map.bucket_size(it) << endl; //该桶中有几个元素

我的理解是：元素先被哈希函数映射到某个bucket，同一条桶内再逐个比较。负载因子=size/bucket_count，一旦超过max_load_factor就会触发rehash扩容。 rehash会搬移所有元素并使全部迭代器失效，这也解释了为什么unordered_map对迭代器失效比vector更“敏感”。

键的修改：extract与merge

这是我认为unordered_map最独特的部分。键作为pair的const成员，是不能直接赋值的，标准库给出了extract()这条正路：

//extract(key)是不重新分配内存情况下唯一可修改map中元素键值的方式
auto node = map.extract("orange");
node.key() = "mongo";//取出节点后修改键
map.insert(std::move(node));//再插回去

extract()把元素以节点句柄的形式取出来，此时可以修改键，随后再插回去，全程不重新分配内存。这比“删旧插新”要省得多。

merge()则是同系列的操作：

unordered_map<string, int> t{{"phone", 5000}, {"computer", 10000}};
map.merge(t);//把t的节点全部搬到map，冲突的留在原地
if (t.empty()) { cout << "t is empty" << endl; }

merge()后t变为空（冲突元素除外），说明它搬移的是节点本身而不是拷贝元素，这与extract()是同一套节点机制。

补充要点

遍历unordered_map得到元素的顺序是不确定的，由哈希结果决定，这一点和vector的顺序遍历完全不同。需要有序时应该换用map，或者自己维护顺序。

小结

unordered_map的核心在于“哈希表”三个字：元素按bucket组织，负载因子决定何时扩容，rehash影响全部迭代器。它独有的extract()/merge()节点机制，则解决了"键不可修改"这个哈希容器特有的限制。

对比vector和string，它们的共通方法让我上手很快，而真正需要花心思的，恰恰是哈希结构带来的这些差异点。

本文所用的测试代码收录于Learncpp，如有不妥之处欢迎指正。