企业官网建设流程全解析

底层数据结构（本质区别）

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（可能是任何顺序）

时间复杂度

注意：

unordered_map最坏情况 O(n)（哈希冲突严重）

map始终稳定 O(log n)

是否有序

多线程下的性能差异

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），以减少冲突、保持插入和查找的效率；

但扩容过程代价较大，会导致性能瞬时下降。