跳表、红黑树、哈希表、B 树的查找复杂度
哪些公司问过
答案要点
- 跳表期望 O(log n)、最坏 O(n),随机层数,Redis 有序集合使用
- 红黑树最坏 O(log n),近似平衡,C++ map 和 Java TreeMap 使用
- 哈希表平均 O(1)、最坏 O(n),不支持有序和范围查询
- B 树多路平衡,树高低、磁盘 IO 少,数据库多用 B+ 树
- 选型看是否需要有序、范围查询以及数据在内存还是磁盘
易错点
- 说哈希表查找就是 O(1),忽略冲突严重时退化
- 说跳表最坏也是 O(log n),其实是期望复杂度
- 混淆 B 树和 B+ 树,B+ 树数据只存在叶子节点
面试官常见追问
- map 和 unordered_map 底层和复杂度有什么区别?
- unordered_map 如何解决哈希冲突?
- 为什么 Redis 有序集合用跳表而不用红黑树?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。