C++ std::unordered_map

std::unordered_map 是 C++ STL 中无序键值对容器的核心成员，底层基于哈希表实现，存储唯一键（key）与对应值（value）的映射关系，且不保证键的顺序。其最大优势是插入、查找、删除操作的平均时间复杂度为 O(1)，适合对效率敏感且无需键有序的场景。
1、底层数据结构与特性

1.1 底层数据结构与核心概念

• 底层结构：哈希表（Hash Table）。
  
• 核心特性：
  
  
  • 关联性：元素是键值对，即 std::pair。
    
  • 无序性：容器中的元素是无序的。元素的存储顺序取决于其键（Key） 的哈希值以及它们如何被映射到桶中。遍历顺序是不确定的。
    
  • 唯一性：集合中每个元素的键（Key） 都是唯一的。
    
  
  
• 实现原理：
  
  
  
  • 容器维护一个桶数组（Array of Buckets）。
    
  • 通过一个哈希函数将元素的键转换成一个哈希值。
    
  • 根据哈希值计算出该元素应该属于哪个桶（通常是 hash_value % bucket_count）。
    
  • 采用链地址法解决哈希冲突，即每个桶是一个链表，所有映射到同一桶的键值对都放在这个链表中。
    
  
  

1.2 核心特性与原理

• 平均常数时间复杂度 (O(1))
  
  
  
  • 在理想情况下，通过键进行的插入、删除和查找操作的平均时间复杂度是常数级的，即 O(1)。这是它最大的优势。
    
  
  
• 最坏情况时间复杂度 (O(n))
  
  
  
  • 在最坏情况下（所有元素都哈希到同一个桶），整个哈希表退化为一个链表，所有操作的时间复杂度变为 O(n)。
    
  
  
• 负载因子与重哈希（Rehashing）
  
  
  
  • 负载因子：load_factor = size() / bucket_count()。
    
  • 当 load_factor > max_load_factor 时，容器会自动执行重哈希（分配新桶数组，重新映射所有元素）。
    
  • 重哈希是一个开销很大的操作，会导致所有迭代器、指针和引用失效。
    
  
  
• 键不可修改，值可修改
  
  
  
  • 元素的键是 const 的，一旦插入就不能修改。
    
  • 元素的值是非 const 的，可以随时修改。
    
  
  

2、操作指导与代码示例

2.1 初始化与构造函数

1. #include <unordered_map>
2. #include <string>
4. // 1. 空unordered_map
5. std::unordered_map<int, std::string> umap1;
7. // 2. 使用初始化列表 (C++11)
8. std::unordered_map<int, std::string> umap2 = {
9.     {1, "Alice"},
10.     {2, "Bob"},
11.     {3, "Charlie"} // 顺序是不确定的！
12. };
14. // 3. 指定初始桶数量（用于性能调优）
15. std::unordered_map<std::string, int> umap3(100); // 创建时约有100个桶
17. // 4. 拷贝构造函数
18. std::unordered_map<int, std::string> umap4(umap2);

复制代码

2.2 元素访问与查找（最核心的操作）

[code]std::unordered_map m = {{1, "Apple"}, {2, "Banana"}};// --- 最常用的访问操作：operator[] ---// 特性：如果键存在，返回对应的值的引用。//       如果键不存在，则会插入一个具有该键的新元素，并将其值进行值初始化，然后返回这个新值的引用。m[1] = "Apricot"; // 修改已存在的键值对：{1, "Apricot"}std::cout