---
title: "C++中unordered_map的一些思考"
date: 2026-09-05
category: "C++"
tags: ["C++", "STL", "unordered_map"]
summary: "引言\\n\\nunordered_map是我接触的第一个哈希容器，之前只知道它“查得快”，对bucket、负载因子这些概念完全没有概念，更不知道map中的键竟然有专门的修改方式。\\n\\n在此篇文章中，我将记录下自己通过一个方法示例实验对unordered_map的理解，重点放在它与其他容器不同的哈希结构上，以供思考，如有不足之处欢迎指正。…"
series:
  name: "C++STL容器及附属"
  order: 0
---

## 引言

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

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

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

## 正文

### 与其他容器共通的部分

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

### 插入与访问

插入有三种常见写法：

```cpp
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()，避免`[]`无意中插入新元素。

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

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

### 哈希结构：bucket与负载因子

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

```cpp
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()这条正路：

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

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

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

```cpp
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](https://github.com/ManJin03/Learncpp)，如有不妥之处欢迎指正。