std::unordered_map / unordered_set（哈希表）

一、概念与底层

• unordered_map / unordered_set（C++11）：无序关联容器，底层是哈希表（拉链法 / 链地址法）。
• unordered_multimap/unordered_multiset：允许重复键。

特点：

• 平均 O(1) 查找 / 插入 / 删除；最坏 O(n)（严重哈希冲突时退化）。
• 遍历无序（bucket 顺序）。
• 不要求 key 有 operator<，而是要求 key 提供哈希函数 std::hash + 判等 operator==。

二、底层结构（chain hash table）

            buckets（vector<node*>）  每个 bucket 是一个链表的头
   ┌──────┬──────┬──────┬──────┬──────┐
   │  B0  │  B1  │  B2  │  B3  │ ...  │
   └──┬───┴──┬───┴──┬───┴──┬───┴──────┘
      ▼      ▼      ▼
    node   node   node
      ▼             ▼
    node          node

• std::hash 计算出 hashcode → bucket_index = hashcode % bucket_count。
• 同 bucket 碰撞的元素用单向链表/数组链拼接。

libstdc++ 实现细节：

• 元素存储在一个**单向链表（_Hashtable 维护）**里，链表按插入顺序/最新访问排列，同时用「bucket 链表」索引加快查找。
• bucket_count 是素数序列：53、97、193、389 …（素数取模减少碰撞聚集）。

三、哈希冲突解决方式（问底层必答）

1. 拉链法（链地址法）：同 bucket 挂链表 —— STL 采用。
2. 开放定址法：冲突时按探测序列找空位（线性探测、二次探测、双重哈希）—— 如很多自定义哈希实现、Java 的 ThreadLocalMap。
3. 再哈希法。
4. 建立公共溢出区。

面试常问：为什么 STL 用拉链法？—— 开放定址在删除时需要「懒惰删除/墓碑」，且装载因子高时性能骤降；拉链法实现简单、删除容易、对装载因子容忍度高，链表短则仍 O(1)。

四、装载因子与扩容（rehash）

• 装载因子 load factor = size / bucket_count，默认 max_load_factor = 1.0。
• 当 size > bucket_count × max_load_factor 时触发 rehash：扩容 bucket 数组到下一个素数，并把现有所有元素重新哈希（放回新的 bucket）—— 这是开销大的 O(n) 操作，且使所有迭代器失效（链表重排）。
• 可用 reserve(n) 预留 buckets 避免频繁 rehash。

五、高频问答

Q1. map vs unordered_map 选型？

维度	map（红黑树）	unordered_map（哈希表）
查找复杂度	O(log n) 稳定	O(1) 平均 / O(n) 最坏
遍历顺序	升序	无序
数据有序性需求	需要 ✅	不需要
key 要求	operator<（或比较器）	std::hash + operator==
缓存/内存	节点分散，略差	buckets 连续 + 节点，性能通常更高（读）
高频插入删除	优秀均衡	佳（无树平衡开销）但可能 rehash
自定义 key 复杂度	简单（重载 <）	需自定义 hash + 等号
适用	有序输出、范围查询、树遍历	大量「按 key 单点查」、不要求有序

工程经验：绝大多数「只需要查字典/计数、不要求有序」场景，unordered_map 更快；需要范围查询、有序遍历、lower_bound 用 map。

Q2. 如何自定义 unordered_map 的 key？

struct Person {
    std::string name;
    int age;
    bool operator==(const Person& o) const {
        return name == o.name && age == o.age;
    }
};
struct PersonHash {
    size_t operator()(const Person& p) const {
        return std::hash<std::string>{}(p.name)
             ^ (std::hash<int>{}(p.age) << 1);   // 组合哈希
    }
};
std::unordered_map<Person, int, PersonHash> m;

必须同时提供哈希和判等；不同 key 哈希值尽量分散（组合时用移位/大质数避免简单 ^ 冲突）；相同 key 哈希必须一致。

Q3. 遍历 unordered_map 是确定的吗？

否：序遍历按 bucket 顺序，与插入顺序、扩容历史无关，无稳定顺序保证。

Q4. 什么情况会退化成 O(n)？

所有元素哈希到同一 bucket（恶意构造 / 差 hash / 有偏 key）。C++ 对 std::hash<string> 有随机化 seed 抗碰撞（部分实现），但自定义 hash 差时仍可能退化。

六、面试追问点

1. 拉链法 vs 开放定址优缺点（上文）。
2. 素数 bucket vs 2 的幂 bucket？—— 素数配合取模减少碰撞聚集（2 的幂可用位运算快，但只取低位，碰撞更严重；Java 用 2 的幂但做了扰动）。
3. 手写简易哈希表通常实现什么？（bucket 数组 + 链表/vector，实现 insert/find/erase、扩容）
4. reserve 传的是预计元素个数还是 bucket 数？—— 是期望的 bucket 数语义（通过 max_load_factor 换算预分配）。