std::unordered_set::find为何比std::find更快？LeetCode算法题实测疑问

题目链接：缺失的第一个正整数

解法1：带正整数过滤的哈希集合解法 #

运行耗时：171个测试用例共471ms

#include <unordered_set>
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        std::unordered_set<int> s;
        for (auto& n: nums)
            if (n > 0)
                s.insert(n);
        int ret = 1;
        while (s.find(ret) != s.end())
            ret++;
        
        return ret;
    }
};

解法2：直接遍历数组查找解法 #

运行结果：超时

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int ret = 1; 
        while(std::find(nums.begin(), nums.end(), ret) != nums.end())
            ret ++;
        return ret;
    }
};

解法3：无过滤的哈希集合解法 #

运行耗时：171个测试用例共394ms

#include <unordered_set>
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        std::unordered_set<int> s;
        for (auto& n: nums)
            s.insert(n);
        int ret = 1;
        while (s.find(ret) != s.end())
            ret++;
        
        return ret;
    }
};

为什么哈希集合方案比直接std::find遍历数组快 #

核心原因是两种方案的时间复杂度存在量级差异：

• 直接调用std::find的方案：std::find本身是线性遍历逻辑，单次查找时间复杂度为O(n)，如果缺失的第一个正整数为k，整体时间复杂度就是O(kn)。极端场景下如果数组包含了1~n的所有正整数，k等于n+1，整体复杂度就达到了O(n²)*，数组规模较大时就会触发超时。
• 哈希集合方案：插入n个元素的平均时间复杂度为O(n)，后续unordered_set::find的单次平均查找复杂度为O(1)，k次查找总复杂度为O(k)，整体平均复杂度为O(n)，性能远高于平方级的遍历方案。

为什么去掉if (n > 0)判断反而耗时更低 #

这是分支判断开销和插入操作开销的权衡结果：

• 带if(n>0)的版本每次循环都要执行一次条件分支判断，现代CPU依赖分支预测提升效率，如果测试用例中正整数占比很高，分支预测失败的概率会上升，带来的性能损耗远大于过滤非正整数节省的插入开销。
• 去掉分支判断后，虽然多插入了一部分非正整数，但这些元素不会影响后续查找逻辑（查找从1开始，非正整数永远不会被命中），反而因为消除了分支判断，循环执行效率更高，最终总耗时更低。

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