调用unordered_set/unordered_map的reserve(new_size)会触发新桶数组分配吗？

你的基本理解是准确的：unordered_set 和 unordered_map 底层依赖桶数组（一般用vector实现），每个桶对应一个链表（部分现代实现会用更高效的结构，但标准允许链表形式），用来存放哈希冲突的键或键值对。

针对你提到的扩容问题，答案是肯定的：当需要更多桶时，容器会触发**重新哈希（rehash）**操作，逻辑和你描述的一致，但和vector::reserve存在细节差异：

• 扩容流程：

  • 首先分配一个更大的新桶数组（桶数通常按翻倍或质数序列增长，具体由实现决定）；
  • 遍历旧桶数组的每个链表，对每个元素重新计算哈希值，找到新桶数组中的对应位置，然后仅转移链表节点的指针——不需要拷贝或移动元素本身，因为链表节点的存储是独立的，只需调整指针指向即可完成元素在桶间的迁移；
  • 最后释放旧桶数组，完成扩容。

• 与vector::reserve的对比：

  • 两者的核心目的类似：vector::reserve是提前分配内存避免频繁扩容，unordered_set/unordered_map的reserve成员函数也是提前设置足够的桶数，避免插入元素时频繁触发rehash；
  • 本质区别在于：vector扩容时需要把元素从旧内存块移动/拷贝到新的连续内存块；而无序容器的rehash仅调整链表指针，元素本身的存储位置不会改变，开销更低（但仍存在哈希计算的成本）。

额外补充：当容器的负载因子（元素总数 / 桶的数量）超过默认阈值（通常为1.0）时，会自动触发rehash。你也可以手动调用rehash(n)强制将桶数设置为至少n，或调用reserve(n)确保容器能容纳n个元素而不触发自动rehash。

内容的提问来源于stack exchange，提问作者Andrey Rubliov