题目

编写程序，探查 std::unordered_map 的底层哈希表（开链哈希桶 Hash Bucket）结构。通过调用 bucket_count()、bucket_size() 与 load_factor()，实时观测元素插入过程中当装载因子突破最大阈值（默认 max_load_factor() == 1.0）时所引发的哈希桶数激增（Rehash）现象，并打印每个桶中由于哈希冲突挂载的链表节点。

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

输出格式：输出装载因子动态变化、哈希桶再分配与桶内链表冲突分布详情。

数据范围与约定：闭散列开链哈希表、平均常数时间复杂度 O(1)。

思路与算法

1. 哈希桶开链模型
std::unordered_map 采用拉链法解决哈希冲突。每个桶（Bucket）是一个单向链表头指针。计算 hash(key) % bucket_count 决定存入哪一个桶。

2. 负载因子与 Rehash
load_factor = size() / bucket_count()。当负载因子超过 max_load_factor 时，哈希表会自动申请约 2 倍数量的新桶，并将所有历史节点重新散列（Rehash），开销为 O(N)。

3. 预先 reserve 防抖动
对于海量已知规模的数据，预先调用 umap.reserve(expected_size)，能将桶数量一次性初始化到位，避免多次 Rehash 带来的高额分配损耗。

完整程序

#include <iostream>
#include <unordered_map>
#include <string>

void inspectBuckets(const std::unordered_map<int, std::string>& map, const std::string& tag) {
    std::cout << "=== [" << tag << "] ===\n";
    std::cout << "元素总数 (size): " << map.size() 
              << ", 哈希桶总数 (bucket_count): " << map.bucket_count() << "\n";
    std::cout << "当前负载因子是否超过阈值: " << std::boolalpha
              << (map.load_factor() > map.max_load_factor()) << "\n";
    size_t nonempty = 0;
    size_t maxChain = 0;
    for (size_t b = 0; b < map.bucket_count(); ++b) {
        size_t n = map.bucket_size(b);
        if (n > 0) ++nonempty;
        if (n > maxChain) maxChain = n;
    }
    std::cout << "非空桶个数: " << nonempty << ", 最长链: " << maxChain << "\n\n";
}

int main() {
    std::unordered_map<int, std::string> studentMap;

    // 初始状态
    inspectBuckets(studentMap, "初始空表");

    // 连续插入促使负载因子升高并触发 Rehash
    for (int i = 1; i <= 15; ++i) {
        studentMap[i] = "Student_" + std::to_string(i);
        if (i == 4 || i == 10 || i == 15) {
            inspectBuckets(studentMap, "插入 " + std::to_string(i) + " 个元素后");
        }
    }

    return 0;
}

运行示例

输出：

=== [初始空表] ===
元素总数 (size): 0, 哈希桶总数 (bucket_count): 1
当前负载因子是否超过阈值: false
非空桶个数: 0, 最长链: 0

=== [插入 4 个元素后] ===
元素总数 (size): 4, 哈希桶总数 (bucket_count): 13
当前负载因子是否超过阈值: false
非空桶个数: 4, 最长链: 1

=== [插入 10 个元素后] ===
元素总数 (size): 10, 哈希桶总数 (bucket_count): 13
当前负载因子是否超过阈值: false
非空桶个数: 10, 最长链: 1

=== [插入 15 个元素后] ===
元素总数 (size): 15, 哈希桶总数 (bucket_count): 29
当前负载因子是否超过阈值: false
非空桶个数: 15, 最长链: 1