STL:map与unordered_map
底层数据结构（本质区别）
map
底层是：红黑树（平衡二叉搜索树）
特点：
自动按 key 排序（默认升序）
插入后依然保持有序
map<int, int> m; m[3] = 30; m[1] = 10; m[2] = 20;输出顺序：
1 2 3
unordered_map
底层是：哈希表
特点：
无序存储
元素位置由 hash 函数决定
unordered_map<int, int> m; m[3] = 30; m[1] = 10; m[2] = 20;输出顺序（不确定）：
2 3 1（可能是任何顺序）
时间复杂度
| 操作 | map | unordered_map |
|---|---|---|
| 查找 | O(log n) | O(1)（平均） |
| 插入 | O(log n) | O(1)（平均） |
| 删除 | O(log n) | O(1)（平均） |
注意：
unordered_map最坏情况 O(n)（哈希冲突严重）
map始终稳定 O(log n)
是否有序
| 容器 | 是否有序 |
|---|---|
| map | 有序 |
| unordered_map | 无序 |
多线程下的性能差异
unordered_map 插入查找快，但线程安全性差，需加锁或使用concurrent_unordered_map
map插入较慢，但访问结构清晰，适合在多线程并发读的场景下做共享（读锁+写锁）
总之在多线程环境下，map 的结构更适合读多写少的场景，配合shared_mutex可以实现并发读。而 unordered_map 虽然查找快，但并不适合直接并发写操作，除非我们通过分桶加锁，或者使用像 TBB 提供的 concurrent_unordered_map 这样的专业并发容器
unordered_map 发生哈希冲突会怎么处理？
当 unordered_map 发生哈希冲突时，会将多个哈希值相同的元素存入同一个哈希桶中，通常通过链表（链式地址法）或开放寻址法来解决；
C++ STL 中一般采用链表方式，即发生冲突的元素会插入到该桶对应链表的末尾，查找时需要遍历该链表，冲突多时会降低查找性能。
为什么 unordered_map 最坏情况是 O(n)？
因为unordered_map 底层是哈希表结构，理论上查找和插入都是 O(1)，但在最坏情况下，所有键的哈希值都一样（哈希冲突极端严重），所有元素都被插入到同一个桶中，退化成了链表结构，此时查找、插入、删除都变成了线性查找，时间复杂度退化为 O(n)。
map 和 unordered_map 的内存占用对比？
map 由于基于红黑树实现，每个节点需要存储指针（父节点、左右子节点）和颜色位，结构更紧凑且稳定；
而 unordered_map 基于哈希表实现，需要额外存储哈希桶数组（包含大量空位）、链表指针等结构，为了降低冲突还要预留扩容空间，因此在元素量相同时，unordered_map 的内存占用通常比 map 更高，但也换来了更快的查找效率（平均 O(1)）。
哈希表的负载因子是啥？扩容机制如何？
哈希表的负载因子（Load Factor）是元素个数（N）与桶个数（B）之比，公式为：α = N / B，表示哈希表的“拥挤程度”；
当负载因子超过某个阈值（例如 0.75），就会触发扩容机制，即重新分配更大的桶数组并对所有元素重新哈希（rehash），以减少冲突、保持插入和查找的效率；
但扩容过程代价较大，会导致性能瞬时下降。