std::unordered_set 的查找时间不是常数

Question

为了找出适合我特定目的的最佳容器类型，我比较了 std::vector、已排序 std::vector 与二分搜索、std::set 和 std::unordered_set 的查找时间。结果如下：

我跳过了对 10'000 多个元素的 std::vector 查找，以保持运行时间有限。容器中充满了从 0 到 n-1 的所有整数，并且查找 100'000 个随机整数。

那里的向量和有序集没有什么大的惊喜，但是 std::unordered_set 发生了什么？查找时间应该是恒定的...由于在某些阈值下重新散列等原因，可能会出现一些波动，但 300'000 个元素之后的上升对我来说看起来很奇怪。有人解释一下吗

代码在 Linux 上编译并运行，GCC 11.3.0 处于发布模式（我认为是 O3）。

编辑：

我做了更多测试：

这里我在构建unordered_set之后调用rehash(n*4)。因此，平均碰撞量和桶中列表的长度应该是恒定的。缓存可能是一个解释，但我不认为查找时间会继续增加。

这是我和 ChatGPT 编写的基准代码：

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

// Custom binary search implementation
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 << ", ";

    // Generate test data
    std::vector<int> testData(n);
    for (int i = 0; i < n; ++i) {
        testData[i] = i;
    }

    // Seed for random number generation
    std::srand(std::time(0));

    if(n < 1e4){
        // Test std::vector lookup time
        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, ";
    }

    // Test sorted std::vector with binary search lookup time
    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() << ", ";

    // Test std::set lookup time
    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() << ", ";

    // Test std::unordered_set lookup time
    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;
}

Answer 1

https://en.cppreference.com/w/cpp/container/unordered_set/find 状态：

平均恒定，最坏情况与容器大小呈线性关系

查找包含对象的存储桶应该始终是恒定时间（受缓存等 CPU 影响），但查找存储桶内的对象取决于该存储桶中的对象数量。

随着容器填满并且每个桶中有多个对象，查找时间将会增加。