C++ STL Hash表扩容策略

C++ STL（Standard Template Library）中的 unordered_map 和 unordered_set 容器使用哈希表（hash table）作为其底层数据结构

1. 当哈希表的负载因子（即已存储元素数量与哈希表大小的比值）达到一定阈值时，哈希表会触发扩容操作。默认情况下，这个阈值是 1.0（即当已存储元素数量达到哈希表大小的两倍时，触发扩容）。负载因子越小，哈希表的性能越好，但空间利用率越低；负载因子越大，哈希表的空间利用率越高，但性能可能降低。

2. 扩容操作通常涉及创建一个新的哈希表，其大小是原哈希表的两倍（或其他预定义的比例）。然后，遍历原哈希表中的所有元素，使用新的哈希函数计算它们在新哈希表中的位置，并将这些元素插入到新哈希表中。

3. 在扩容过程中，unordered_map 和 unordered_set 会保持元素的相对顺序。这意味着，如果两个元素在原哈希表中具有相同的哈希值，它们在新哈希表中也将具有相同的哈希值，并且它们的相对顺序将保持不变。

4. 扩容操作可能会导致一定程度的性能下降，因为需要重新计算元素在新哈希表中的位置并将它们插入到新哈希表中。然而，由于哈希表的负载因子始终保持在一个合理的范围内，因此这种性能下降通常不会对程序产生显著影响。

总之，C++ STL 中的 unordered_map 和 unordered_set 容器使用了一种基于哈希表的实现，当哈希表的负载因子达到一定阈值时，会自动触发扩容操作以保持性能。在扩容过程中，这些容器会保持元素的相对顺序。