C++实现两数之和时unordered_map性能比map慢3倍的原因咨询

求解两数之和问题时编写的两份算法核心逻辑完全一致，仅存储容器分别选用unordered_map和有序map，具体实现如下：

unordered_map版本实现 #

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> d;
        int indx {0};
        for(auto num: nums){
            int complement {target - num};
            if(d.find(complement) != d.end()) {
                vector<int> answer {d[complement], indx};
                return answer;
            } else {
                d[num] = indx;
                indx++;
            }
        }
    return vector<int> {-1, -1};
    }
};

有序map版本实现 #

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> d;
        int indx {0};
        for(auto num: nums){
            int complement {target - num};
            if(d.find(complement) != d.end()) {
                vector<int> answer {d[complement], indx};
                return answer;
            } else {
                d[num] = indx;
                indx++;
            }
        }
    return vector<int> {-1, -1};
    }
};

对两种容器底层复杂度的认知没有错误：unordered_map基于哈希表实现，插入、查询均摊时间复杂度为O(1)；map基于红黑树实现，单步操作时间复杂度为O(logn)。实际测试中出现unordered_map速度慢三倍的反直觉现象，主要来自几个实际运行层面的影响因素：

• 哈希冲突带来的常数开销飙升：O(1)是理想均摊值，int类型的默认哈希函数直接用原值作为哈希值，平台测试用例中存在部分刻意构造的整数序列，会触发大量哈希冲突。此时哈希表的查询/插入需要遍历桶内的冲突链表，实际开销远高于红黑树的固定比较次数。两数之和的测试用例输入规模普遍不大，n大多在10^3~104区间，log2(n)最多仅14次指针跳转和值比较，比冲突状态下哈希表的哈希计算、桶定位、冲突链表遍历总开销更低。
• rehash操作的额外开销：unordered_map默认初始化的桶数量很小，随着元素插入，负载因子达到阈值时会触发全表rehash，即重新分配更大的桶数组、对所有已有元素重算哈希值、迁移到新桶位置，这个过程的突发内存和计算开销在小数据量场景下占比极高。而map每次插入仅需分配单个红黑树节点、做局部的树旋转调整，没有批量重排的额外开销。
• 小数据量下的缓存与测量偏差：map的红黑树节点访问路径在小数据量下缓存局部性表现并不差，加上在线判题时单次用例运行时间极短，系统调度、CPU缓存状态的随机波动很容易放大性能差异，三倍的速度差并不能代表两种容器在大规模数据下的真实性能表现——如果把输入规模提升到10^6级别，哈希表的均摊复杂度优势就会显现，性能会反超有序map。

如果要优化unordered_map版本的性能，可以在初始化时提前预留足够的桶空间d.reserve(nums.size())，减少rehash次数，速度会有明显提升。

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