C++11引入的STL中的unordered系列关联式容器

前言

C++11 引入了四个无序关联容器：std::unordered_map、std::unordered_set、std::unordered_multimap、std::unordered_multiset。它们位于<unordered_map>与<unordered_set>两个头文件中，底层基于哈希表，平均情况下查找、插入、删除是常数时间。在此之前，标准库只有以红黑树实现的std::map/std::set，查找是对数时间且有序。

最常见的误解是「unordered 一定比 map 快」。哈希表的平均常数时间建立在「哈希函数把键均匀打散」之上；如果大量键落入同一个桶，单次操作会退化为线性。标准只规定平均复杂度，最坏情况仍是 O(n)。另一个误解是「无序容器的遍历顺序是随机的」——顺序不是随机的，而是由哈希值、桶数量和实现细节共同决定，对同一份数据在同一次运行中通常是稳定的，但标准不保证任何顺序，也不保证不同运行之间一致，因此不能依赖。

还有一类问题出在自定义键类型上：只写了operator==却没提供哈希函数，或者哈希函数与相等语义不一致，编译能过但查不到元素。本文按「模型—接口—自定义键—失效规则—工程实践」的顺序讲解。

一、哈希表模型与复杂度

无序容器把元素放进若干个桶（bucket），每个元素根据Hash计算出的值决定进入哪个桶。查找时先算哈希、定位桶，再在桶内比较键是否相等。标准没有规定桶内用链地址法还是开放寻址，也没有规定桶的数量如何增长，但通过一组 bucket 接口暴露了「桶」这个抽象：

哈希表的性能核心是负载因子。负载因子越高，桶内平均元素越多，比较次数越多；负载因子低则内存占用大。rehash会重新分配桶数组并把元素重新分布，是一次 O(n) 的操作。标准不保证rehash的具体时机，只规定插入后若导致负载因子超过max_load_factor()，容器会执行 rehash；实现也可以在其它时机 rehash。

复杂度要说准确：平均情况 O(1)，最坏情况 O(n)（所有键冲突到同一个桶）。这里的「平均」是对哈希函数在键集合上的分布做的假设，不是对任意输入都成立的保证。

二、四个容器的差异

注意unordered_map的value_type中键是const的：不能通过迭代器修改键，否则会破坏哈希结构。要「改键」只能删除旧元素再插入新元素。

operator[]的行为需要说清：如果键不存在，它会插入一个值初始化的映射值并返回引用；如果存在，返回已有值的引用。因此它要求mapped_type可默认构造。只想查询时用find或at：

// 适用于 C++17
#include <iostream>
#include <string>
#include <unordered_map>

int main() {
std::unordered_map<std::string, int> freq;
for (const char* w : {"a", "b", "a", "c", "a"}) {
++freq[w]; // 键不存在时插入 {w, 0}，再自增
}

std::cout << freq.at("a") << ' ' << freq.count("z") << '\n';

auto it = freq.find("b");
if (it != freq.end()) {
std::cout << it->second << '\n';
}

for (const auto& kv : freq) {
std::cout << kv.first << '=' << kv.second << '\n';
}
}

at在键不存在时抛出std::out_of_range；count返回 0 或 1（对 multi 版本可能大于 1）；find返回迭代器或end()。三者的选择取决于语义：确定存在用at，只判断存在用count，需要访问值又不想异常用find。

multi 版本用equal_range取出所有等价键：

// 适用于 C++17
#include <iostream>
#include <string>
#include <unordered_map>

int main() {
std::unordered_multimap<std::string, int> mm;
mm.emplace("apple", 1);
mm.emplace("apple", 2);

auto range = mm.equal_range("apple");
for (auto it = range.first; it != range.second; ++it) {
std::cout << it->second << ' ';
}
}

equal_range的返回类型是std::pair<iterator, iterator>，两个迭代器构成半开区间。注意 multi 容器不保证等价元素在遍历中相邻，equal_range的结果覆盖全部等价元素，但不承诺顺序。

三、自定义键类型

要让自定义类型作为键，需要提供哈希函数与相等比较。默认的std::equal_to<Key>调用operator==，默认的std::hash<Key>只对标准库已支持的类型有特化，自定义类型必须自己提供。推荐把哈希写成函数对象，通过第三个模板参数传入，而不是特化std::hash——前者更局部，也不会污染标准命名空间。

// 适用于 C++17
#include <cstddef>
#include <functional>
#include <string>
#include <unordered_map>

struct Point {
int x;
int y;

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

struct PointHash {
std::size_t operator()(const Point& p) const {
std::size_t h1 = std::hash<int>{}(p.x);
std::size_t h2 = std::hash<int>{}(p.y);
// 组合两个哈希值；常数取自常见的 hash_combine 写法，非标准规定
return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2));
}
};

int main() {
std::unordered_map<Point, std::string, PointHash> names;
names.emplace(Point{1, 2}, "origin-ish");
names[Point{3, 4}] = "far";
}

有两条硬性约束。第一，相等的键必须产生相同的哈希值：若a == b，则必须有hash(a) == hash(b)。违反这一点，容器会把相等的键放进不同的桶，查找必然失败。第二，哈希函数应当是纯函数，对同一对象多次调用返回相同结果；用地址、时间或随机数做哈希会破坏容器的不变式。

如果键的相等语义是「忽略大小写」，那么哈希也必须忽略大小写，否则两个被判定相等的字符串会得到不同哈希值。这类不一致是自定义键最常见的 bug。

另外，std::hash对字符串等类型的实现不保证抗碰撞。如果键来自不可信输入（例如 HTTP 头、JSON 字段），攻击者可以构造大量同桶键，把平均 O(1) 退化为 O(n)，形成算法复杂度攻击。防御手段包括限制输入规模、使用带密钥的哈希（如各实现提供的非标准接口，或自行引入成熟的哈希库），不要把std::hash当作安全设施。具体可用的带密钥哈希设施以你的标准库或第三方库文档为准。

四、迭代器、引用与 rehash

无序容器的失效规则与std::vector不同，需要单独记住：

rehash 只改变元素所在的桶和遍历顺序，不移动元素对象本身（节点式实现），因此指向元素的指针和引用保持有效。这一点常被误解为「rehash 后所有东西都失效」。但迭代器会失效，因为迭代器需要记录桶的位置。

基于这个规则，有两种常见写法需要避免：

// 错误：rehash 后继续使用保存的迭代器
auto it = m.find(key);
m.reserve(10000); // 可能触发 rehash
use(it->second); // 迭代器可能已失效

// 正确：保存指针或键
auto* p = &it->second; // 指向元素，rehash 后仍有效
m.reserve(10000);
use(*p);

不过依赖「引用在 rehash 后仍有效」需要确认你的实现确实采用节点式存储；标准对无序容器的引用稳定性有保证，但如果你使用的是非标准容器或自定义分配器，仍应查阅文档。

erase的返回值在 C++11 起是「被删元素之后的迭代器」，因此遍历删除可以写成：

// 适用于 C++17
for (auto it = m.begin(); it != m.end(); ) {
if (shouldRemove(*it)) {
it = m.erase(it);
} else {
++it;
}
}

不要写m.erase(it++);这种旧习惯，虽然对某些容器可行，但语义不如使用返回值清晰。

五、工程实践建议

第一，插入大量已知数量的元素前调用reserve(n)。它不是语义要求，但能减少中途 rehash 的次数；具体收益取决于实现和负载因子，不应给出未经测量的倍数。

第二，不要依赖遍历顺序。需要按 key 排序输出时，把元素拷贝到std::vector再用std::sort，或者直接使用std::map。需要按插入顺序遍历时，标准无序容器做不到，需要额外的链表维护顺序。

第三，键类型尽量用标准库已支持哈希的类型（整数、std::string、指针等）。自定义键要同时检查==与哈希的一致性，并写单元测试覆盖「相等键哈希相同」这一性质。

第四，对不可信输入保持警惕。哈希碰撞攻击是真实存在的，防御侧的做法是限制请求规模、设置超时、必要时使用带密钥的哈希；不要自行实现密码学哈希。

常见坑点

1. 
   
2. ❌ 依赖unordered_map的遍历顺序，认为它按插入顺序或哈希值排序。
3. 
   

✅ 标准不保证任何顺序；需要顺序就排序或改用有序容器。

1. 
   
2. ❌ 自定义键只写operator==，直接把类型作为unordered_map的键。
3. 
   

✅ 同时提供哈希函数对象，作为第三个模板参数传入。

1. 
   
2. ❌ 哈希忽略大小写而operator==区分大小写，或反之。
3. 
   

✅ 哈希与相等语义必须一致：相等则哈希相同。

1. 
   
2. ❌ 用m[key]做查询，结果意外插入了新元素。
3. 
   

✅ 查询用find/at/count；operator[]的语义是「不存在则插入」。

1. 
   
2. ❌ 认为无序容器任何情况下都是 O(1)。
3. 
   

✅ 平均 O(1)，最坏 O(n)；大量哈希冲突时退化为线性。

1. 
   
2. ❌ 在for循环中erase(it)后仍执行++it。
3. 
   

✅ 用it = m.erase(it)，C++11 起返回下一个位置。

1. 
   
2. ❌ 认为 rehash 会让指向元素的指针和引用失效。
3. 
   

✅ rehash 使迭代器失效，但指向元素的引用和指针仍然有效。

1. 
   
2. ❌ 把std::hash<std::string>当作抵御恶意输入的安全哈希。
3. 
   

✅ 它不保证抗碰撞；对不可信输入限制规模，必要时使用带密钥哈希。

总结

无序容器的价值在于「以空间换常数时间」，但这个常数依赖哈希质量与负载因子。把它当成「更快的 map」而不理解桶模型，就容易在自定义键、迭代器失效和恶意输入上出问题。先确认键的哈希与相等一致，再根据访问模式选择reserve与容器类型，才是稳妥的用法。