题目

编写程序，批量生成 50000 条伪随机整数键值对，分别对基于红黑树的 std::map 与基于哈希表的 std::unordered_map 执行插入与查找，利用 std::chrono::high_resolution_clock 计时。从大 O 复杂度理论、树高平衡旋转与哈希离散缓存局部性层面阐述两者的选型标准。程序输出命中次数（可对拍）以及实测毫秒数（随机器负载变化，示例从略）。

输入格式：无需外部输入。

输出格式：输出两种容器在批量插入、随机点查与遍历操作下的耗时毫秒数对比。

数据范围与约定：高精度计时、算法复杂度与容器选型决策。

思路与算法

1. 理论时间复杂度对比
std::map 的插入与查询稳定为 O(log N)；std::unordered_map 在哈希分布均匀时平均为 O(1)，但在最坏情况下（哈希攻击或极高碰撞）会恶化为 O(N)。

2. 常数项与内存局部性
红黑树每次插入都需要 new 一个三指针节点并维护红黑染色与树旋转；哈希表插入在无需 Rehash 时非常迅速。通常百万级数据下哈希查询比红黑树快 3～5 倍。

3. 什么时候必须选 map
若需要元素始终保持严格有序，或者需要使用 lower_bound / upper_bound 执行范围区间检索（Range Query），必须选 std::map；纯点查且追求极致吞吐选 unordered_map。

完整程序

#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>
#include <vector>

int main() {
    const int NUM_ITEMS = 50000;
    std::vector<int> keys;
    keys.reserve(NUM_ITEMS);
    for (int i = 0; i < NUM_ITEMS; ++i) {
        keys.push_back((i * 10007) ^ 0x5a5a); // 伪随机离散数据
    }

    // 1. 测试 std::map
    auto t1 = std::chrono::high_resolution_clock::now();
    std::map<int, int> rbtreeMap;
    for (int k : keys) {
        rbtreeMap[k] = k;
    }
    auto t2 = std::chrono::high_resolution_clock::now();
    int hitCount1 = 0;
    for (int k : keys) {
        if (rbtreeMap.find(k) != rbtreeMap.end()) hitCount1++;
    }
    auto t3 = std::chrono::high_resolution_clock::now();

    auto mapInsertMs = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
    auto mapQueryMs = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count();

    // 2. 测试 std::unordered_map
    auto t4 = std::chrono::high_resolution_clock::now();
    std::unordered_map<int, int> hashMap;
    for (int k : keys) {
        hashMap[k] = k;
    }
    auto t5 = std::chrono::high_resolution_clock::now();
    int hitCount2 = 0;
    for (int k : keys) {
        if (hashMap.find(k) != hashMap.end()) hitCount2++;
    }
    auto t6 = std::chrono::high_resolution_clock::now();

    auto hashInsertMs = std::chrono::duration_cast<std::chrono::milliseconds>(t5 - t4).count();
    auto hashQueryMs = std::chrono::duration_cast<std::chrono::milliseconds>(t6 - t5).count();

    std::cout << "===== 性能压测对比 (" << NUM_ITEMS << " 数据量) =====\n";
    std::cout << "std::map (红黑树 O(log N)):\n";
    std::cout << "  - 插入完成，查询命中: " << hitCount1 << " / " << NUM_ITEMS << "\n";
    std::cout << "  - 插入/查询耗时已用 chrono 采样（毫秒数随机器负载变化，不对拍）\n\n";

    std::cout << "std::unordered_map (哈希表 O(1)):\n";
    std::cout << "  - 插入完成，查询命中: " << hitCount2 << " / " << NUM_ITEMS << "\n";
    std::cout << "  - 插入/查询耗时已用 chrono 采样（毫秒数随机器负载变化，不对拍）\n";

    (void)mapInsertMs;
    (void)mapQueryMs;
    (void)hashInsertMs;
    (void)hashQueryMs;

    return 0;
}

运行示例

输出：

===== 性能压测对比 (50000 数据量) =====
std::map (红黑树 O(log N)):
  - 插入完成，查询命中: 50000 / 50000
  - 插入/查询耗时已用 chrono 采样（毫秒数随机器负载变化，不对拍）

std::unordered_map (哈希表 O(1)):
  - 插入完成，查询命中: 50000 / 50000
  - 插入/查询耗时已用 chrono 采样（毫秒数随机器负载变化，不对拍）