17370845950

std::unordered_map 用的是开链法（separate chaining）

标准规定，std::unordered_map 必须提供平均常数时间的查找/插入/删除，而 C++11 起明确要求其底层采用「桶 + 单链表」结构处理哈希冲突，也就是开链法。每个桶（bucket）存储一个指向节点链表的指针，冲突键值对被挂到同一桶的链表上。

冲突发生时，新节点总是插在链表头部

这是 libstdc++（GCC）和 libc++（Clang）的共同实现策略，不是标准强制，但已成为事实标准。好处是避免遍历链表找尾部，插入为 O(1)（不计哈希计算）。但注意：

• 迭代器遍历桶内元素时，顺序是「后插入的在前」，和插入顺序相反
• 如果你依赖「同桶内元素的相对顺序」，比如手写调试打印，会看到逆序
• 链表节点内存不连续，频繁冲突会加剧缓存不友好

桶数量动态增长，负载因子触发 rehash

std::unordered_map 维护一个 max_load_factor()（默认 1.0），当 size() / bucket_count() > max_load_factor() 时，自动扩容并 rehash 所有元素。关键点：

• rehash 后桶数量通常翻倍（如 1 → 2 → 4 → 8 → …），但具体倍数由实现决定
• rehash 是全量操作，O(N) 时间，可能引发短暂停顿
• 调用 reserve(N) 可预先分配足够桶，避免多次 rehash；它等价于确保 bucket_count() >= N

自定义类型做 key 时，哈希和相等必须匹配

开链法依赖两个函数协同工作：Hash 决定进哪个桶，KeyEqual（默认 std::equal_to）在链表内逐个比对。常见错误：

立即学习“C++免费学习笔记（深入）”；

• 只重载了 operator==，却没提供对应哈希特化，导致编译失败
• 哈希函数返回值不稳定（如含指针地址、std::time(nullptr)），造成查找失效
• 两个逻辑相等的对象（a == b 为 true）返回不同哈希值，它们会被分到不同桶，永远无法查到

struct Point {
    int x, y;
    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
};
namespace std {
template<> struct hash {
    size_t operator()(const Point& p) const {
        // 正确：x 和 y 都参与，且顺序一致
        return hash{}(p.x) ^ (hash{}(p.y) << 16);
    }
};}