C++哈希表：unordered_set与unordered_map全解析

发布时间：2026/7/19 1:23:59

1. 无序容器的定位

C++11 引入了四个基于哈希表的无序容器：

std::unordered_set —— 不重复元素的集合，无序

std::unordered_multiset —— 允许重复元素的集合，无序

std::unordered_map —— 键值对，键不重复，无序

std::unordered_multimap —— 键值对，键可重复，无序

今天介绍最常用的 unordered_set 和 unordered_map。

2. 头文件和声明

#include <unordered_set> // unordered_set, unordered_multiset #include <unordered_map> // unordered_map, unordered_multimap

声明对象：

std::unordered_set<int> uset; // 存放 int 的无序集合 std::unordered_map<std::string, int> umap; // string → int 的无序映射

与 set/map 不同的是，不需要指定比较器（因为没有排序），但可以指定哈希函数和键相等判定。

3. unordered_set 的基本操作

3.1 插入元素

std::unordered_set<int> uset; uset.insert(10); uset.insert(20); uset.insert(10); // 重复，不会插入 uset.emplace(30); // 原地构造

insert 也返回 pair<iterator, bool>，second 表示是否成功插入。

3.2 查找元素

if (uset.find(20) != uset.end()) { std::cout << "找到了 20\n"; } if (uset.count(10)) { std::cout << "10 存在\n"; }

count 要么返回 0 要么 1。

3.3 删除元素

uset.erase(20); // 按键值删除 auto it = uset.find(30); if (it != uset.end()) uset.erase(it); // 按迭代器删除 uset.clear();

3.4 遍历

for (const auto& x : uset) { std::cout << x << " "; } // 或用迭代器 for (auto it = uset.begin(); it != uset.end(); ++it) { std::cout << *it << " "; }

注意：遍历顺序是无规律的，与插入顺序无关，也绝不是排序顺序。千万不要依赖遍历顺序。

4. unordered_map 的基本操作

unordered_map 存储的是 std::pair<const Key, T> 的键值对，用法与 map 非常相似，只是内部无序。

4.1 插入和修改

std::unordered_map<std::string, double> price; price.insert({"apple", 3.5}); price.insert(std::make_pair("banana", 2.0)); price.emplace("orange", 4.2); // 使用 []，若键不存在则插入默认值，然后赋值 price["grape"] = 5.5; price["apple"] = 3.8; // 修改已存在键的值

[] 的隐藏风险：如果访问一个不存在的键，umap["unknown"] 会插入一个 {unknown, 0} 的默认值对。若只想查询而不插入，务必使用 find 或 at。

std::cout << price.at("apple") << "\n"; // 存在，输出 3.8 // price.at("pear"); // 不存在，抛出 std::out_of_range 异常 auto it = price.find("banana"); if (it != price.end()) { std::cout << it->second << "\n"; }

4.2 遍历

for (const auto& p : price) { std::cout << p.first << " : " << p.second << "\n"; } // C++17 结构化绑定 for (const auto& [name, price] : price) { std::cout << name << " costs " << price << "\n"; }

同样，遍历顺序是无序的。

5. 哈希表性能的关键：哈希函数与负载因子

5.1 什么是哈希函数？

哈希表将键通过哈希函数映射到一个整数值，然后根据这个值决定元素存放在哪个“桶”里。理想情况下，每个桶中的元素很少，查找就是 O(1)。

C++ 标准库为内置类型（int, std::string, 指针等）提供了默认的哈希函数。但如果你的键是自定义类型，就需要自己提供哈希函数，并可能提供相等比较函数。

5.2 自定义类型作为键

假设我们有一个 Point 结构体：

struct Point { int x, y; bool operator==(const Point& other) const { return x == other.x && y == other.y; } };

我们需要为它写一个哈希函数：

struct PointHash { size_t operator()(const Point& p) const { // 一种简单的组合哈希方法 return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1); } };

然后声明容器：

std::unordered_set<Point, PointHash> points; points.insert({1, 2});

对于 unordered_map，需要指定键的哈希和相等比较（值不需要）：

std::unordered_map<Point, std::string, PointHash> pointNames; pointNames[{0, 0}] = "原点";

若等号运算符有特殊逻辑，也可以自定义相等仿函数作为第二个模板参数（在哈希之后）。

5.3 桶与接口

哈希表由一系列“桶”组成，每个桶是一个链表（或后继结构）。标准库提供了一些探查哈希表状态的接口：

std::unordered_map<std::string, int> umap; // ... 插入数据 std::cout << "桶的个数: " << umap.bucket_count() << "\n"; std::cout << "负载因子: " << umap.load_factor() << " ( = " << umap.size() << " / " << umap.bucket_count() << " )\n"; std::cout << "最大负载因子: " << umap.max_load_factor() << "\n"; // 遍历所有桶 for (size_t i = 0; i < umap.bucket_count(); ++i) { std::cout << "桶 " << i << " 有 " << umap.bucket_size(i) << " 个元素:"; for (auto it = umap.begin(i); it != umap.end(i); ++it) { std::cout << " " << it->first; } std::cout << "\n"; }

5.4 重哈希与性能

负载因子 = 元素个数 / 桶的数量。当 load_factor() > max_load_factor() 时，容器会自动进行重哈希（rehash），分配更多的桶并重新分配所有元素。这是一个较重的操作（O(n)）。

你可以在插入大量元素前使用 reserve(n) 预留桶的数量，避免反复重哈希。

umap.reserve(1000); // 为至少 1000 个元素预留足够的桶

也可以直接调用 rehash(n) 手动设置桶的最小数量。

最佳实践：已知要插入 N 个元素时，调用 reserve(N)；或在插入前预估数量，避免多次重哈希。

6. unordered_map / unordered_set vs map / set

特性 set / map unordered_set / unordered_map
底层数据结构红黑树（平衡 BST）哈希表
顺序性元素始终有序无序
查找复杂度 O(log n) 平均 O(1)，最坏 O(n)
插入/删除复杂度 O(log n) 平均 O(1)，最坏 O(n)
遍历顺序按键升序（或自定义）无序，可能随插入而变
内存占用较小（每个节点两个指针+颜色）较大（桶数组 + 链表节点）
迭代器失效插入永不失效，删除仅当前失效重哈希时所有迭代器失效；删除仅当前失效
适用场景需要顺序遍历、范围查询单纯快速查找、无需排序

选用建议：

如果需要字典序输出或范围查找（比如找出所有大于某值的键），用 map/set。

如果只需要“键是否存在”或“快速获取值”，且不关心顺序，用 unordered_map/unordered_set。