跳表相比哈希表的优势
哪些公司问过
阿里巴巴控股1
答案要点
- 跳表元素有序,支持范围查询、排名、前驱后继,哈希表做不到
- 跳表期望 O(log n),哈希表平均 O(1) 但冲突严重时最坏 O(n)
- 跳表没有整体 rehash,插删只改局部指针,延迟平稳
- 局部修改便于实现并发,如 Java 的 ConcurrentSkipListMap
- 代价是单点查找较慢、多层指针占内存,Redis zset 两者组合使用
易错点
- 说跳表最坏也是 O(log n),忽略这是期望复杂度
- 认为跳表在所有场景都优于哈希表,忽略精确查找时哈希更快
- 忽略多层指针带来的额外内存开销
面试官常见追问
- 跳表的时间复杂度是多少?
- 跳表的层数怎么决定?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场