字典(哈希表)插入与查找的时间复杂度
哪些公司问过
答案要点
- 哈希表插入、查找平均 O(1),大量冲突时最坏 O(n)
- 扩容需要整体 rehash,单次 O(n),按倍数扩容后插入均摊 O(1)
- 冲突解决方式有链地址法与开放寻址法,影响最坏性能和缓存友好性
- Java HashMap 桶内链表过长会树化,最坏可降至 O(log n)
- 平衡二叉树插入查找稳定 O(log n),优势是有序、支持范围查询
易错点
- 只答 O(1) 不提平均与最坏情况的区别
- 忽略扩容 rehash 的成本以及均摊分析
- 把所有语言的字典实现都当成链表法,不了解开放寻址与树化
面试官常见追问
- 平衡二叉树的插入时间复杂度是多少?
- 哈希表最坏 O(n) 在实际中如何缓解?
- 哈希表和红黑树如何选择?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。