平衡树与哈希表两类数据结构的对比
哪些公司问过
答案要点
- 平衡树按 key 有序,增删查最坏 O(log n),支持范围查询、前驱后继、有序遍历
- 哈希表平均 O(1),无序、不支持范围查询,冲突严重时会退化
- 哈希表扩容 rehash 有一次性开销,平衡树没有这种抖动
- 精确查找追求吞吐选哈希;需要有序或最坏延迟可控选平衡树
易错点
- 说哈希表任何情况都是 O(1),忽略冲突退化和扩容开销
- 认为平衡树一定比哈希慢,忽略常数、缓存局部性和数据规模
- 混淆 C++ map 与 unordered_map 的底层实现
面试官常见追问
- 哈希表最坏情况为什么会退化?Java 怎么缓解?
- Redis 有序集合为什么用跳表而不是平衡树?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场