为何unordered_map::rehash最坏为二次复杂度，operator[]却为线性？

你看到的operator[]复杂度描述并不完整，完整的描述应该包含两部分：

平均情况：常数，最坏情况：与大小呈线性关系。
如果插入触发了重哈希，平均情况与元素数量呈线性，最坏情况为二次。

这就和rehash的复杂度描述对应上了，两者并不矛盾，具体拆解如下：

• rehash的最坏二次复杂度：
  当所有元素的哈希值完全相同（极端哈希碰撞场景），重哈希时需要将每个元素重新插入新哈希表。由于所有元素都会落到同一个桶中，每个元素插入前都要遍历该桶已有的全部元素，n个元素的总操作量为O(n²)，这是单次rehash操作的最坏情况。

• operator[]的两种最坏情况：

  1. 未触发重哈希时：如果插入的元素对应的桶因哈希碰撞聚集了O(n)个元素，插入前需要遍历整个链表确认元素是否存在，此时单次操作的最坏复杂度为O(n)（线性）。
  2. 触发重哈希时：此时operator[]的复杂度等价于rehash的复杂度，最坏情况为O(n²)（二次），这部分是你之前看到的描述里缺失的内容。

另外需要注意，C++标准允许rehash存在最坏二次的实现，但要求operator[]的分摊复杂度为常数——也就是说，即使某次operator[]触发了O(n²)的重哈希，这个开销会被分摊到之前的多次插入操作中，长期来看平均每次操作的复杂度仍为常数。

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