unordered_map 底层实现、哈希冲突与 rehash
哪些公司问过
答案要点
- 底层是桶数组加链表的哈希表,用链地址法解决哈希冲突
- 负载因子 = 元素数 / 桶数,默认最大负载因子为 1.0,超过即 rehash
- rehash 分配更多桶并重新分布所有元素,迭代器失效,元素的引用和指针仍有效
- 哈希函数差、键分布集中或恶意构造冲突时,查找退化为 O(n)
- 可用 reserve 预分配桶,自定义键需提供哈希函数和相等比较
易错点
- 把 Java HashMap 链表转红黑树的机制套到 C++ unordered_map 上
- 以为 rehash 后指向元素的指针也失效
- 以为哈希表所有操作都是严格 O(1)
面试官常见追问
- map 和 unordered_map 有什么区别?
- C++ 的 unordered_map 冲突多了会转红黑树吗?
- 如何避免频繁 rehash?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- vector 的扩容机制与性能174 场
- map 与 unordered_map 的区别167 场
- STL 的组成与常用容器151 场
- vector 与 list 的区别85 场
- STL 迭代器失效的场景47 场
- map 的底层实现:为什么用红黑树47 场
- STL 内存分配器12 场
- deque 的底层实现10 场
- vector 和数组的区别8 场
- 迭代器的作用与分类7 场