map 与 unordered_map 的区别
哪些公司问过
答案要点
- map/set 底层是红黑树:key 有序,增删查 O(log n)
- unordered_map/set 底层是哈希表:key 无序,平均 O(1),最坏 O(n)
- map 支持有序遍历和 lower_bound/upper_bound 范围查询;unordered_map 不支持
- unordered_map 在 rehash 时迭代器失效(元素的引用和指针仍有效);map 插入不会使任何迭代器失效
- 自定义 key:map 需要 operator<(或比较器),unordered_map 需要哈希函数和 operator==
易错点
- 说 unordered_map 一定比 map 快:数据量小或哈希质量差时未必,最坏还会退化
- 忘记 unordered_map 的遍历是无序的
- 用自定义类型做 key 却只提供了 operator<:unordered_map 需要哈希和 ==
- 用 operator[] 做查询导致意外插入
面试官常见追问
- map 为什么用红黑树而不用 AVL 树?
- unordered_map 的哈希冲突怎么处理?
- map 的 operator[] 有什么坑?
- 什么时候选 map,什么时候选 unordered_map?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- vector 的扩容机制与性能174 场
- STL 的组成与常用容器151 场
- vector 与 list 的区别85 场
- STL 迭代器失效的场景47 场
- map 的底层实现:为什么用红黑树47 场
- STL 内存分配器12 场
- deque 的底层实现10 场
- unordered_map 底层实现、哈希冲突与 rehash9 场
- vector 和数组的区别8 场
- 迭代器的作用与分类7 场