C++ std::unordered_map

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

1、底层数据结构与特性

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

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

1.2 核心特性与原理

1. 平均常数时间复杂度 (O(1))

   • 在理想情况下，通过键进行的插入、删除和查找操作的平均时间复杂度是常数级的，即 O(1)。这是它最大的优势。

2. 最坏情况时间复杂度 (O(n))

   • 在最坏情况下（所有元素都哈希到同一个桶），整个哈希表退化为一个链表，所有操作的时间复杂度变为 O(n)。

3. 负载因子与重哈希（Rehashing）

   • 负载因子：load_factor = size() / bucket_count()。
   • 当 load_factor > max_load_factor 时，容器会自动执行重哈希（分配新桶数组，重新映射所有元素）。
   • 重哈希是一个开销很大的操作，会导致所有迭代器、指针和引用失效。

4. 键不可修改，值可修改

   • 元素的键是 const 的，一旦插入就不能修改。
   • 元素的值是非 const 的，可以随时修改。

2、操作指导与代码示例

2.1 初始化与构造函数

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

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

std::unordered_map<int, std::string> m = {{1, "Apple"}, {2, "Banana"}};// --- 最常用的访问操作：operator[] ---
// 特性：如果键存在，返回对应的值的引用。
//       如果键不存在，则会插入一个具有该键的新元素，并将其值进行值初始化，然后返回这个新值的引用。
m[1] = "Apricot"; // 修改已存在的键值对：{1, "Apricot"}
std::cout << m[2]; // 输出: Banana
std::cout << m[3]; // 键3不存在！这会执行插入操作：m[3] = ""。现在map中有3个元素。// --- 安全的查找操作：find() ---
// 推荐在需要“只读”访问时使用find，因为它不会改变map。
auto it = m.find(2);
if (it != m.end()) { // 必须检查是否找到！std::cout << "Found: " << it->first << " -> " << it->second << "\n";it->second = "Blueberry"; // 可以修改值// it->first = 4; // 错误！键是const的，不能修改。
} else {std::cout << "Key not found.\n";
}// --- 检查存在性：count() ---
// 对于unordered_map，返回值只能是0或1。
if (m.count(4) == 0) {std::cout << "Key 4 is not present.\n";
}// --- at()：带边界检查的访问 ---
// 如果键存在，返回对应的值的引用。
// 如果键不存在，抛出 std::out_of_range 异常。
try {std::string value = m.at(5); // 键5不存在，会抛出异常
} catch (const std::out_of_range& e) {std::cout << "Key not found: " << e.what() << '\n';
}

2.3 增加元素

std::unordered_map<int, std::string> umap;// 1. insert: 插入一个pair
// 方法一：make_pair
auto ret1 = umap.insert(std::make_pair(1, "One"));
// 方法二：使用{}构造pair (C++11)
auto ret2 = umap.insert({2, "Two"});// ret 的类型是 std::pair<iterator, bool>
// ret.first: 指向被插入元素（或已存在元素）的迭代器
// ret.second: 插入是否成功（true表示成功，false表示键已存在）
if (ret2.second) {std::cout << "Insertion of key 2 succeeded.\n";
}// 2. emplace: 原地构造，避免临时对象（高效！）
// 直接传递构造键和值所需的参数给emplace
auto ret3 = umap.emplace(3, "Three"); // 直接在map内部构造pair(3, "Three")
if (ret3.second) {std::cout << "Emplace succeeded.\n";
}// 3. try_emplace (C++17): 更安全高效的emplace
// 如果key不存在，则用参数构造value。
// 如果key已存在，则什么都不做，且不会构造value对象。这对于构造开销大的value类型非常关键。
auto ret4 = umap.try_emplace(3, "Third"); // 键3已存在，不会构造"Third"，ret4.second为false
auto ret5 = umap.try_emplace(4, "Four"); // 键4不存在，构造"Four"，ret5.second为true// 4. operator[]: 如上所述，如果键不存在会执行插入。
umap[5] = "Five"; // 如果5不存在，则插入{5, ""}，然后赋值"Five"

2.4 删除元素

std::unordered_map<int, std::string> umap = {{10, "A"}, {20, "B"}, {30, "C"}, {40, "D"}};// 1. erase by key: 删除键为30的元素，返回删除的元素个数（0或1）
size_t numErased = umap.erase(30); // numErased = 1// 2. erase by iterator: 删除指定位置的元素，更高效
auto it = umap.find(20);
if (it != umap.end()) {umap.erase(it);
}// 3. erase by range: 删除一个区间的元素 [first, last)
// (不常用，因为元素无序)
auto first = umap.find(40);
auto last = umap.end();
umap.erase(first, last); // 删除40

2.5 遍历元素

std::unordered_map<std::string, int> cityPopulations = {{"Beijing", 2154},{"Shanghai", 2424},{"Guangzhou", 1404}
};// 1. 范围for循环 + 结构化绑定 (C++17) - 最清晰，推荐！
for (const auto& [city, pop] : cityPopulations) {std::cout << city << ": " << pop << "万人\n";
}
// 输出顺序不确定// 2. 范围for循环 (C++11)
for (const auto& pair : cityPopulations) {std::cout << pair.first << ": " << pair.second << "万人\n";
}// 3. 使用迭代器
for (auto it = cityPopulations.begin(); it != cityPopulations.end(); ++it) {std::cout << it->first << ": " << it->second << "万人\n";
}

2.6 容量与性能管理（重要！）

std::unordered_map<int, std::string> umap;// 1. 预留空间：避免多次重哈希，提升性能的关键！
// 如果你事先知道要插入1000个元素，调用reserve可以避免插入过程中多次重哈希。
umap.reserve(1000); // 预留至少能容纳1000个元素的空间// 插入大量元素...
for (int i = 0; i < 1000; ++i) {umap[i] = "value";
}// 2. 查看当前状态
std::cout << "Size: " << umap.size() << "\n";
std::cout << "Bucket count: " << umap.bucket_count() << "\n"; // 桶的数量（通常是质数）
std::cout << "Load factor: " << umap.load_factor() << "\n"; // 当前负载因子
std::cout << "Max load factor: " << umap.max_load_factor() << "\n"; // 最大负载因子（默认~1.0）// 3. 手动重哈希：强制将桶数调整为至少 n
umap.rehash(2000); // 强制桶数 >= 2000// 4. 修改最大负载因子
umap.max_load_factor(0.75f); // 设置更小的最大负载因子，减少冲突概率，但增加内存使用// 5. 查看哈希表状态（调试用）
for (size_t i = 0; i < umap.bucket_count(); ++i) {std::cout << "Bucket #" << i << " has " << umap.bucket_size(i) << " elements.\n";
}

2.7 自定义类型作为键

要让自定义类型作为键，你需要提供：

1. 哈希函数：计算键的哈希值。
2. 相等比较函数：判断两个键是否相等。

2.7.1 特化 std::hash 并重载 operator==（推荐）**

struct Point {int x;int y;// 1. 必须重载 operator==bool operator==(const Point& other) const {return x == other.x && y == other.y;}
};// 2. 特化std::hash模板
namespace std {template<>struct hash<Point> {size_t operator()(const Point& p) const {// 使用良好的哈希组合技术size_t h1 = hash<int>()(p.x);size_t h2 = hash<int>()(p.y);return h1 ^ (h2 << 1);// 更好的方式：使用hash_combine（见下文）}};
}// 使用
std::unordered_map<Point, std::string> pointMap;
pointMap[{1, 2}] = "Origin";

2.7.2 提供自定义的哈希器和相等比较器

struct Point {int x;int y;
};// 自定义哈希器
struct PointHash {size_t operator()(const Point& p) const {return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);}
};// 自定义相等比较器
struct PointEqual {bool operator()(const Point& a, const Point& b) const {return a.x == b.x && a.y == b.y;}
};// 使用
std::unordered_map<Point, std::string, PointHash, PointEqual> pointMap;

2.7.3 更好的哈希组合方法（减少冲突）

// 一个通用的哈希组合函数（来自Boost等库的理念）
template <class T>
inline void hash_combine(std::size_t& seed, const T& v) {std::hash<T> hasher;seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}struct PointHash {size_t operator()(const Point& p) const {std::size_t seed = 0;hash_combine(seed, p.x);hash_combine(seed, p.y);return seed;}
};

3、常见问题

1. std::unordered_map 的底层实现是什么？
   底层是哈希表。它维护一个桶数组，通过哈希函数将键映射到桶的索引，并使用链地址法解决哈希冲突。

2. operator[] 和 find() 方法的主要区别是什么？

• operator[] 如果找不到键，会插入一个具有该键的新元素（值初始化），并返回其值的引用。它会改变map。
• find() 仅仅进行查找，返回一个迭代器，如果没找到则返回 end()，它不会改变map。在只读检查存在性时，应优先使用 find()。

3. 什么是重哈希？它何时发生？有什么影响？
   重哈希是哈希表扩容的过程。当当前负载因子超过最大负载因子时，容器会自动分配一个更大的新桶数组，并重新映射所有元素。重哈希会导致所有迭代器、指针和引用失效，并且是一个性能开销较大的操作。

4. 如何让一个自定义类型可以作为 unordered_map 的键？
   需要提供两个东西：

   1. 哈希函数：通过特化 std::hash 模板或提供自定义的哈希函数对象。
   2. 相等比较函数：通过重载 operator== 或提供自定义的相等比较函数对象。

5. 如何提高 unordered_map 的性能？

   1. 调用 reserve(n)：在插入大量元素前预分配空间，避免多次重哈希。
   2. 提供高质量的哈希函数：减少哈希冲突。
   3. 调整 max_load_factor：降低最大负载因子可以减少冲突，但会增加内存使用。

6. try_emplace 和 emplace 有什么区别？(C++17)
   当键已存在时，emplace 仍然会构造值对象（虽然不会插入），然后将其丢弃，这可能导致不必要的构造开销。try_emplace 在键已存在时不会构造值对象，因此对于构造开销大的值类型，try_emplace 更高效。

7. 什么时候该用 unordered_map，什么时候该用 map？
   当你需要极快的查找速度（平均O(1)），并且不关心元素的顺序时，应该选择 unordered_map。当你需要元素按键有序，或者需要进行范围查询（如找最小/最大的键），或者担心最坏情况的性能时，应该选择 map。

8. 如何避免 std::unordered_map 的 rehash 操作？
   提前用 reserve(n) 预留足够桶数（n 大于预期最大元素数），确保元素数 ≤ 最大负载因子 × 桶数，从而避免自动 rehash。例如：

unordered_map<int, int> um;
um.reserve(1000);  // 预计存储1000个元素，提前预留桶