STL 中的无序容器（Unordered Containers）是 C++11 引入的重要组件，它们与传统的关联容器（如 std::map）最大的区别在于底层实现：无序容器基于哈希表（Hash Table），而有序容器基于红黑树。

---

一、 无序容器家族成员

STL 提供四种无序容器，其接口与有序版本高度相似：

1. std::unordered_map: 存储键值对，键唯一。

2. std::unordered_set: 仅存储键，键唯一。

3. std::unordered_multimap: 键可重复。

4. std::unordered_multiset: 键可重复。

---

二、 底层原理：哈希表 (Hash Table)

无序容器的高效性源于哈希表。

1. 核心架构：开链法 (Separate Chaining)

STL 默认使用开链法处理哈希冲突。

• 桶 (Buckets)：容器内部维护一个数组，数组的每个元素称为一个“桶”。

• 链表 (Nodes)：每个桶指向一个单向链表，所有哈希值相同的元素都存在同一个桶的链表中。

2. 时间复杂度

• 理想情况：$O(1)$。哈希函数均匀分布，每个桶只有一个元素。

• 最坏情况：$O(n)$。所有元素哈希碰撞，退化为单链表。

3. 关键组件

• Hash Function：将键映射到索引。

• Key Equal：当哈希冲突时，通过 operator== 判断两个键是否真的相等。

---

三、 核心知识点与性能指标

1. 负载因子 (Load Factor)

负载因子定义为：load_factor = 容器元素总数 / 桶的总数。

• max_load_factor()：默认通常为 1.0。

• Rehash (重新哈希)：当负载因子超过最大阈值时，容器会自动扩容，重新分配桶并重排所有元素。这是一个 $O(n)$ 的高开销操作。

2. 迭代器失效

• 插入操作：如果触发了 rehash，所有迭代器都会失效；否则，迭代器有效。

• 删除操作：仅指向被删除元素的迭代器失效。

3. 自定义键类型

如果你想使用自定义类作为 unordered_map 的键，必须提供：

1. 哈希函数：特化 std::hash<YourClass>。

2. 相等比较：重载 operator==。

---

四、 无序 vs 有序：如何选择？

特性	有序容器 (map/set)	无序容器 (unordered_)
底层实现	红黑树 (平衡二叉树)	哈希表
查找复杂度	$O(\log n)$	平均 $O(1)$，最坏 $O(n)$
元素顺序	按键排序 (严格弱序)	无序
内存开销	较低	较高 (需预留桶空间)
适用场景	需要范围查找、有序遍历	追求极致的单点查找速度

---

五、 性能优化技巧

1. 预分配空间：如果你知道大概要存多少数据，使用 reserve(count)。这可以避免多次 rehash 带来的性能抖动。

2. 合适的哈希函数：对于自定义类型，确保哈希函数分布均匀，否则会导致严重的哈希冲突。

3. 桶操作分析：利用 bucket_count() 和 bucket_size() 接口可以监控容器当前的健康状况（是否分布不均）。

---

六、 常用 API 摘要

C++

std::unordered_map<string, int> myMap;

// 1. 插入
myMap["apple"] = 1;
myMap.insert({"banana", 2});

// 2. 查找
if (myMap.find("apple") != myMap.end()) { /* ... */ }

// 3. 容量与桶
size_t n = myMap.bucket_count(); // 桶的数量
float f = myMap.load_factor();   // 当前负载因子