文档目录

一、std::map 红黑树的物理布局

std::map<int, string> m;
m[5] = "five";
m[3] = "three";
m[7] = "seven";

内存中的红黑树结构:
堆地址 0x1000: 节点 3 [left=null|right=0x2000|parent=0x3000|color=RED  |"three"]
堆地址 0x2000: 节点 7 [left=null|right=null |parent=0x3000|color=BLACK|"seven"]
堆地址 0x3000: 节点 5 [left=0x1000|right=0x2000|parent=null|color=BLACK|"five" ]
        ↑
        | (根节点，平衡二叉树)

遍历时的缓存表现：每次通过指针跳到下一节点，和 list 一样——缓存命中率极低。

面试高频题：“为什么 map 的插入是 $O(\log N)$ 但实际可能比 unordered_map 的 $O(1)$ 更快？”

  • 当 N 很小（< 1000）时，红黑树的 $\log N$ 大约 10 次比较，而哈希表需要计算哈希值（几十条指令）+ 取模 + 可能的冲突解决。
  • 哈希表在元素少时，负载因子低，桶空间浪费大，缓存命中率比红黑树还差。

二、std::unordered_map 开链哈希表

unordered_map<int, string> um;
um.max_load_factor(1.0);

桶数组 (Bucket Array, 连续内存):
+───────+───────+───────+───────+───────+
| 桶 0  | 桶 1  | 桶 2  | 桶 3  | ...  |
+───┬───+───┬───+───┬───+───┬───+───┬───+
    │       │       │       │
    ▼       ▼       ▼       ▼
   节点     节点     nullptr 节点
   [5]     [13]             [7]
    │       │                │
    ▼       ▼                ▼
  nullptr  nullptr          nullptr
  每个桶指向一个单向/双向链表的头节点

Rehash 的代价：

for (int i = 0; i < 100000; ++i) {
    um[i] = "value"; // 可能触发多次 rehash
}

Rehash 内部流程：

  1. 分配新桶数组（通常是旧大小的 2 倍）。
  2. 遍历所有节点，重新计算 hash(key) % new_bucket_count，把节点挂到新桶上。
  3. 释放旧桶数组。

Rehash 的 3 个性能灾难：

  • $O(N)$ 时间复杂度：100 万个元素 rehash 一次可能要几百毫秒。
  • 所有迭代器失效：和 vector 扩容一样，桶数组指针变了。
  • Cache 大清洗：新桶数组 + 重新链接节点，所有缓存行失效。

高性能教训：可以预先知道元素数量时，用 reserve(N) 提前分配桶空间。

三、容器选择速查

场景 推荐 原因
遍历为主、随机访问 vector 连续内存，缓存友好
两端插入、不需要随机访问 deque 两端 $O(1)$，无扩容搬移
中间插入/删除频繁 list 插入/删除 $O(1)$，但遍历极慢
有序键值查找 map 红黑树 $O(\log N)$
无序键值查找、海量数据 unordered_map 均摊 $O(1)$，小心 rehash