为何std::unordered_set的查找时间并非恒定？

初始测试与疑问 #

为确定特定场景下的最佳容器类型，对比了std::vector、带二分查找的排序std::vector、std::set及std::unordered_set的查找耗时，测试结果如下：

查找时间对比图：横轴为容器元素数量，纵轴为查找耗时（微秒），测试针对100000个随机整数执行查找操作；当元素数量超过10000时，跳过了std::vector的查找测试，容器内填充0到n-1的全部整数。

std::vector和std::set的结果符合预期，但std::unordered_set的表现存在异常：理论上其查找时间应为恒定时间复杂度（O(1)），即使考虑阈值重哈希等因素有波动，元素数量超过300000后的耗时持续上升也不符合预期。

测试环境：Linux系统，GCC 11.3.0，Release模式（推测为O3优化）编译。

编辑1：手动重哈希后的测试 #

为排除重哈希影响，在构建std::unordered_set后调用rehash(n*4)，理论上可让平均冲突数及桶中链表长度保持恒定，测试结果如下：

查找对比图2：展示手动重哈希后各容器的查找耗时，std::unordered_set的耗时仍随元素数量上升而增加。

怀疑是缓存问题，但无法理解为何耗时会持续上升。

编辑2：桶数与数据存储规模的验证测试 #

开展两组高分辨率测试：

1. 桶数增至10倍的测试：验证是否会让性能骤降点出现在1/10的元素量时，结果如下：

10倍桶数测试图：元素数量不变，桶数增至10倍后，std::unordered_set的性能变化趋势未出现预期的提前骤降。

2. 不同数据存储大小的测试：测试存储单个int和存储10个int数组的std::unordered_set，哈希及operator==仅使用数组首个元素。若性能下降源于缓存，预期存储10个int的容器性能骤降点应出现在存储单个int容器的1/10元素量时，但实际结果并非如此：

单int与10int数组查找对比图：展示两种存储类型的std::unordered_set查找耗时，性能骤降点未按缓存预期的比例出现。

编辑3：移出随机数生成后的性能变化 #

将rand()调用移出时间测量范围后，性能提升幅度远超预期（原以为交替查找随机向量和set会引发更多缓存未命中，但实际缓存机制并非如此），测试结果如下：

移除rand后的查找性能图：std::unordered_set的耗时稳定性显著提升，但仍存在随元素数量上升的趋势。

基准测试代码 #

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <chrono>
#include <cstdlib>
#include <ctime>

// 自定义二分查找实现
bool binarySearch(const std::vector<int>& vec, int target) {
    int left = 0, right = vec.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (vec[mid] == target) {
            return true;
        } else if (vec[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

void testLookupTime(int n, int k) {
    std::cout << "[" << n << ", ";

    // 生成测试数据
    std::vector<int> testData(n);
    for (int i = 0; i < n; ++i) {
        testData[i] = i;
    }

    // 随机数生成种子
    std::srand(std::time(0));

    if(n < 1e4){
        // 测试std::vector查找时间
        auto start = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < k; ++i) {
            int randomNum = std::rand() % (n + 1);
            volatile std::vector<int>::iterator result = std::find(testData.begin(), testData.end(), randomNum);
        }
        auto end = std::chrono::high_resolution_clock::now();
        std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << ", ";
    }
    else{
        std::cout << "0, ";
    }

    // 测试排序std::vector（二分查找）的查找时间
    std::sort(testData.begin(), testData.end());
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < k; ++i) {
        int randomNum = std::rand() % (n + 1);
        volatile bool result = binarySearch(testData, randomNum);
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << ", ";

    // 测试std::set查找时间
    std::set<int> testSet(testData.begin(), testData.end());
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < k; ++i) {
        int randomNum = std::rand() % (n + 1);
        volatile std::set<int>::iterator result = testSet.find(randomNum);
    }
    end = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << ", ";

    // 测试std::unordered_set查找时间
    std::unordered_set<int> testUnorderedSet(testData.begin(), testData.end());
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < k; ++i) {
        int randomNum = std::rand() % (n + 1);
        volatile std::unordered_set<int>::iterator result = testUnorderedSet.find(randomNum);
    }
    end = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << "],\n" << std::flush;
}

int main() {
    const int kTimes = 100000;

    for(float n=5; n<=1e8; n*=1.1){
        testLookupTime(n, kTimes);
    }

    return 0;
}

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