C++解答LeetCode无重复最长子串题时，为何unordered_map比map运行更慢？

预期和实际的性能偏差 #

基于算法复杂度的固有认知是完全符合教科书定义的：

• unordered_map基于哈希表实现，插入、查找操作均摊时间复杂度为O(1)，执行n次操作的整体复杂度为O(n)
• std::map基于红黑树实现，插入、查找操作时间复杂度为O(log n)，执行n次操作的整体复杂度为O(n log n)

但在LeetCode提交《无重复字符的最长子串》题目的实测结果完全和预期相反：相同逻辑仅替换容器的前提下，unordered_map版本运行耗时140ms，std::map版本仅耗时40ms。

对应的unordered_map实现版本代码如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        int start=0, mx=0;
        unordered_map<char, int>um;
        
        for(int i=0; i<s.size(); i++)
        {
            if(um.count(s[i]) && start<=um[s[i]])//exists
                start=um[s[i]]+1;
            else 
                mx=max(mx, i-start+1);
                
            um[s[i]]=i;
            cout<<mx<<"\n";
        }
        return mx;
    }
};

性能倒挂的核心原因 #

• 小key、小数据量下，常数项的影响远大于渐进复杂度
  这是最核心的因素：char类型的取值范围仅256个可能值，哪怕最坏情况所有字符都不重复，std::map里最多也只存256个节点。
  此时红黑树的查找最多只需要8次整数比较（log2(256)=8），这种级别的比较是CPU单周期就能完成的操作，固定开销极低。
  反观unordered_map，哪怕实现再高效，单次查找也需要经过哈希值计算、桶位置定位、桶内元素遍历三个步骤，固定开销远高于几次整数比较——O(1)的优势只有在数据规模足够大、能摊薄这些固定成本时才会体现，小数据量下低常数的O(log n)天然更有优势。
• 代码本身存在对unordered_map不友好的重复访问
  循环逻辑里对同一个key做了两次独立哈希查找：先调用count()判断key是否存在，命中后又通过um[s[i]]读取对应的value值，相当于把哈希表的操作数直接翻倍。两次独立哈希操作的总固定开销，已经超过了std::map单次查找带log级别的开销。
• 代码中隐藏的额外拖速操作
  循环内逐次调用cout<<mx<<"\n"输出，LeetCode判题环境下的标准IO刷新本身有较高开销，这个开销对两个容器版本是均等的，但会进一步放大unordered_map本身的高固定成本的劣势。
• 标准库unordered_map的通用实现缺陷
  为了适配任意类型的key，unordered_map的哈希函数、桶管理逻辑都做了通用性妥协，没有针对char、int这类基础小key做专门优化；默认的负载因子、预分配策略也偏保守，短运行流程下的初始化、扩容开销完全没有摊薄空间。
• 本题的更优实现逻辑
  因为key是char类型，完全不需要用哈希表或红黑树，直接定义长度为256的int数组记录每个字符最近出现的位置，单次数组访问的开销远低于两种map，运行速度会比std::map版本再快一个量级。

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