c++oding="utf-8" ?>
std::unordered_map 底层采用开链法（桶+单链表），冲突时新节点插链表头部，遍历呈逆序；负载因子超限触发rehash，reserve可预分配桶；自定义key需同时提供匹配的哈希与相等函数。
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）在链表内逐个比对。常见错误：
- 只重载了
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<point> {
size_t operator()(const Point& p) const {
// 正确：x 和 y 都参与，且顺序一致
return hash<int>{}(p.x) ^ (hash<int>{}(p.y) <p>
开链法本身简单，但实际性能高度依赖哈希函数质量——坏哈希会让所有键挤进少数桶，把平均 <code>O(1)</code> 退化成 <code>O(N)</code>。别只盯着容器接口，先盯住你的 <code>hash<t>::operator()</t></code>。</p></int></int></point>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
