【底层机制】std::unordered_map 扩容机制

底层机制相关推荐阅读：

【C++基础知识】深入剖析C和C++在内存分配上的区别]

【底层机制】【C++】vector 为什么等到满了才扩容而不是提前扩容？

【底层机制】malloc 在实现时为什么要对大小内存采取不同策略？

【底层机制】剖析 brk 和 sbrk的底层原理

【底层机制】为什么栈的内存分配比堆快？

【底层机制】右值引用是什么？为什么要引入右值引用？

【底层机制】auto 关键字的底层实现机制

正文如下：

我们将从为什么需要扩容、如何触发扩容、扩容的具体步骤以及如何优化四个方面来详细讲解。

一、核心概念：为什么需要扩容？

std::unordered_map 是一个基于哈希表实现的关联容器。其理想的查找、插入、删除时间复杂度是 O(1)。实现这一目标的关键在于：

1. 哈希函数 (Hash Function)：将键（Key）均匀地映射到一个大的数值空间。
2. 桶数组 (Bucket Array)：一个连续的内存块，每个位置是一个“桶”（Bucket），是链表的头节点或树的根节点（在冲突严重时）。
3. 解决冲突：通常采用链地址法（Separate Chaining），即同一个桶内的元素以一个链表存储。

问题在于：如果键值对的数量（size()）不断增加，而桶的数量（bucket_count()）保持不变，会导致每个桶后面的链表变得越来越长。这样，操作的效率就会从 O(1) 退化为 O(n)，失去了哈希表的优势。

解决方案：当键值对数量与桶数量的比值（即负载因子 Load Factor）超过某个阈值时，对桶数组进行扩容（Rehashing），即创建一个更大的新桶数组，然后将所有已有的键值对重新哈希到新数组中。

二、触发条件：何时进行扩容？

扩容的触发由一个关键参数控制：最大负载因子 (max_load_factor)，其默认值通常是 1.0。

触发条件可以用一个简单的公式表示： if (load_factor() > max_load_factor()) { rehash(); }

其中：

• 当前负载因子 (load_factor()) = size() / bucket_count()
• 最大负载因子 (max_load_factor())：默认为 1.0，你可以通过 map.max_load_factor(0.7) 来修改它。

具体触发时机： 通常在插入新元素（insert(), emplace(), operator[]）之后，容器会检查负载因子。如果超过最大负载因子，就会自动触发扩容和重哈希过程。

示例： 假设一个 unordered_map 当前有 8 个桶，存有 8 个元素。负载因子为 8 / 8 = 1.0。

• 如果 max_load_factor 是默认的 1.0，此时再插入一个元素，负载因子将变为 9 / 8 = 1.125 > 1.0，触发扩容。
• 如果你事先设置了 map.max_load_factor(2.0)，那么插入第9个元素不会触发扩容，负载因子 1.125 < 2.0，它会继续使用当前的桶数组，直到插入第17个元素（17/8=2.125>2.0）时才会触发。

三、扩容过程详解：一步一步发生了什么？

扩容过程，标准库中的术语是 重哈希 (Rehashing)。这是一个成本很高的操作，其步骤如下：

第1步：分配新的、更大的桶数组

• 新桶数组的大小不是简单地在原有基础上+1。标准库通常会选择一个大于当前 bucket_count() 的、合适的素数作为新的大小。
• 这个选择策略是为了保证哈希值在新桶数组上能够更均匀地分布。GCC/Clang 的 libstdc++ 和 Microsoft 的 MSVC STL 都维护了一个内部的素数数组，扩容时通常会取下一个（或接近两倍的）素数。
  • 例如，当前桶数是 11，扩容后可能变为 23。

第2步：重新计算每个元素的哈希和桶位置

• 遍历原哈希表中的每一个桶，以及每个桶中的每一个元素（节点）。
• 对于每个元素，用其键的哈希值和新桶数组的大小（new_bucket_count）重新计算它应该属于哪个新桶： new_bucket_index = hash(key) % new_bucket_count （实际上标准库使用更高效的方法，如 hash(key) & (new_bucket_count - 1)，但这要求新大小是2的幂，有些实现如MSVC这样做；而GCC使用素数大小，则用取模）。

第3步：节点迁移

• 这是一个非常关键且需要仔细处理的步骤。节点的内存本身不会被释放和重新创建。
• 标准库会直接将原链表中的节点（_Hash_node）解下来，然后插入到新桶数组对应的新链表中。这个过程只涉及指针的修改，避免了昂贵的键值对的拷贝构造或移动构造。
• 注意：在C++17之前，节点迁移可能会涉及哈希值的缓存和复用优化。一些实现会预先计算并存储键的哈希值，在重哈希时就直接使用这个存储的值，避免了重复调用哈希函数，这是一个重要的性能优化。

第4步：交换并释放旧数组

• 将内部指向桶数组的指针改为指向新创建的数组。
• 安全地释放旧的桶数组内存。

重要特性：迭代器失效

• 在重哈希过程中，所有迭代器都会失效。
• 但是，指向元素的指针和引用不会失效。这是因为节点本身在迁移过程中只是被重新链接，其内存地址没有变化。这意味着，即使发生了扩容，你之前通过 &element 获取的地址仍然是有效的。

  std::unordered_map<int, std::string> map = {{1, "one"}, {2, "two"}};
  const auto* ptr = &map[1]; // 获取元素地址
  
  // 进行大量插入，触发多次扩容和重哈希...
  for(int i = 0; i < 10000; ++i) {
      map[i*10] = "value";
  }
  
  std::cout << ptr->second << std::endl; // 仍然是 "one"，指针依然有效！
  std::cout << &map[1] << std::endl;     // 输出地址可能与ptr相同，也可能不同，
                                         // 但ptr指向的内存内容未被破坏。
  

四、性能影响与优化建议

重哈希是一个非常昂贵的操作，其时间复杂度是 O(n)，其中 n 是容器中元素的数量。在高性能场景下，我们需要尽量避免它发生在关键路径上。

优化策略：

1. 预分配空间 (reserve) 这是最重要也是最有效的优化手段。如果你能提前知道大致要存放多少元素，可以直接预留足够数量的桶。

   std::unordered_map<int, Data> big_map;
   big_map.reserve(1000000); // 直接分配足以容纳100万个元素的桶
   // 接下来插入100万个元素的过程中，将完全避免重哈希！
   

   reserve(n) 会计算需要至少多少个桶才能使得存放 n 个元素后负载因子不超过最大值，然后直接进行一次重哈希到目标大小。

2. 调整最大负载因子 (max_load_factor) 如果你希望节省内存，可以适当降低最大负载因子（例如设为 0.7）。这会让哈希表更“稀疏”，查找效率更高，但会更早地触发扩容，消耗更多内存。 如果你希望减少重哈希次数（对插入性能不敏感），可以适当提高最大负载因子（例如设为 1.5或2.0）。这会使得链表更长，查找效率下降，但重哈希的次数会变少。

3. 在批量插入之前操作 如果需要一次性插入大量已知数据，最好在插入之前一次性调用 reserve()。这比让哈希表自己一次次被动扩容要高效得多。

总结

理解 unordered_map 的扩容机制，能帮助你在“时间”和“空间”之间做出明智的权衡，写出更稳定、高效的C++程序。