unordered_set扩容如何影响性能？相关技术疑问咨询

1. unordered_set的insert操作是否会因内部扩容变为O(n)？ #

是的，当unordered_set内部哈希桶数组需要扩容时，单次insert操作的时间复杂度会退化为O(n)。因为扩容过程需要遍历所有现有元素，将它们重新分配到新的哈希桶数组中，这个过程的开销是线性的。

不过要注意，均摊时间复杂度仍然是O(1)。扩容不会每次insert都触发，通常只有当负载因子（元素总数/桶的数量）超过阈值（默认一般为1.0）时才会执行，且扩容后桶数通常翻倍，平均下来每次insert的开销还是常数级的。

2. 提前扩容再插入是否能降低时间复杂度？ #

是的。如果提前调用reserve(n)设置足够大的桶数，让后续插入元素不会触发自动扩容，那么所有insert操作的时间复杂度都会稳定在O(1)。

这是因为提前扩容后，插入元素时无需再复制、迁移现有元素，只需要计算哈希值、定位对应桶并处理冲突（若存在）即可，彻底避免了扩容时的线性时间开销。对于批量插入大量元素的场景，提前调用reserve是很实用的优化手段。

3. 扩容无需重哈希的观点是否正确？ #

这个观点不正确。unordered_set扩容时必须执行重哈希，原理在于：哈希桶的索引是通过元素哈希值 % 桶数计算得到的。当桶数改变后，原索引的计算逻辑失效，必须重新计算每个元素的哈希定位（或用原哈希值对新桶数取模），才能将元素放到新数组的正确桶位中。

如果不重哈希，元素会被放置到错误的桶位置，后续的查找、插入、删除操作都会因无法通过哈希定位到正确位置而失效。

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