10倍通过率！跳表、红黑树、B+树、HashMap 高频面试题总结（附参考答案+避坑指南）
大家好，这是大厂面试拆解--数据结构与算法系列的第2篇文章
如果你面试 或者工作中遇到相关问题，欢迎留言！
阅读本文 你获得如下收益
- ✅ 通过跳表了解，数组，哈希表，红黑树，B+ 数据结构不同使用场景。
- ✅ 从感觉理解 Map 容器 采用红黑树，Redis为采用跳表，Mysql采用B+ 存储 升级准确理解。
- ✅坚持思考，就会很酷！有错误的地方，请大家指正。这次采用对比 和可视化演示加速理解。
- 直接回答跳表有什么优点 不好回答？哈希表不支持范围查询，在坏情况下 查询性能退化o（n），跳表解决支持范围查询和 top k 查询。
- 直接回答跳表有什么优点 不好回答？ 红黑树在输入有序数据，导致 不“平衡方式”，然后调整？跳表通过概率方式 保证与输入数据无关，插入链表后 不需要再调整 “平衡”
大纲如下：
用户故事
面试官：什么是跳表（Skip List）？
小义：我开始认真思考这个问题：
- 之前我研究得很透彻，但现在因为连续加班半年，已经忘得一干二净了，不知该如何回答。
- 紧张，自责，说出来你可能不信。
老王：打住，忘记很正常
- 过去半年想不明白的事情，就算再给你半年也想不明白
- 离开面试现场这个环境，回答到工作场景中去，同样因为加班这事情个优先级 高于学习这个事情，导致不停的推迟，无奈推迟，最后忘记。
- 可能感觉无用，可能是不知道从哪里下手 才是隐藏冰山下真正阻力，
- 就像一只公鸡投入长时间研究却仍然不会，会觉得丢人吗？同行会怎么看？其他鸡又会怎么看。 才是隐藏冰山下真正阻力
老王： 现在就是最好的时候，不是课下回家 在学习 。
- 现在你就是面试官，你刷题无数，这次你来面试别人一次，
- 现在你就是一个丰富经验的项目经理，你最清楚方案，这次你就来讨论这次方案
- 现在你就是领导，你根本不懂开发这个事情，这次你用权利让别人想你汇报。
画外音：
- 面试最忌讳的，需求是别人分析，代码是别人设计的，问题是别人解决--我干了啥
- 职场忌讳：什么有价值事情做什么，不是在不停加班1年做无用事情，别人不会多看你一眼睛， 职场不是慈善机构，判断事情标准发生变化。这也是什么整天开会，确定优先级，确定问题紧急程度。
- 想一想 哪怕不能100%去了解，但是看到了，听到，见到了，从第一行原理了解，私下吃饭 时候交流了？尝试上级争取了吗，不要受限于岗位，分工 ，这样不可控因素印象。
小义：
（1）假如我根本不懂 --->我就问
- 什么是跳表，
- 什么场景使用
- 什么场景不会使用
画外音：
- 我不了解，我等着你告我？让我相信。
- 太细节我听不懂，但是场景能使用，什么场景不能使用 我还是了解的。
（2） 假如我了解单链表，你了解到
- 单链表如何删除我清楚，必须查找到前面要一个元素。
- 单链表如何插入我清楚，至少定义2个指针。
-----> 我就会问 跳表插入，删除，查询步骤是什么？
（3）假如软件开发中经常使用 unordered_map，你了解到
- 数据结构是哈希表（hash table或者HashMap ，又称散列表，查询的平均时间复杂度 O(1)
- 哈希表 的key是唯一的，但是不同的key可能产生相同的hashCode，不同hashCode都落通一个bucket桶呢，在最坏情况下，查询时间时间复杂度复杂度 O(n)
- 在jdk1.8版本后，Java对HashMap做了改进，在链表长度大于8的时候，将后面的数据存在红黑树中，以加快检索速度
-----> 我就问：跳表是怎么查询的，时间 复杂度多少？
画外音：
- 链表查询一个元素时候，时间复杂度是o（n），不要发明新 算法，换个跳表这个结构可以吗？
- 能不活学活用 用跳表代替红黑树。
（4）假如你知道你在实时系统中经常使用map 存储业务数据。
- 经常用操作就是插入操作，删除操作 ，
- 并且 删除一个元素,其他迭代器（无论前向或后向）依然保持有效，不会受到影响。
- 红黑树天然更容易配合 STL 的语义（迭代器、顺序、稳定性）
- map 不支持并发，不考虑红黑树并发的问题。
-----> 我就问：什么情况下 redis为什么要使用skiplist跳表，不用 红黑树，hash表
画外音：
- 红黑树维护树的高度上没有AVL树，但是在插入和删除旋转较少更少，更适实时更新业务
- 不考虑并发问题
（5） 假如 我了解一点mysql数据库
- 查询：无法将数据全部加载进内存 ，需要将数据索引信息（主键），存储内存中，一般采用B+ 树索引
- 4 层的 B+ 存储220 亿条： MySQL InnoDB 的实现，假设每个节点大小为 16KB，每个键为 8 字节，每个指针为 6 字节，则每个键指针对占用 14 字节。因此，每个非叶子节点最多可以包含约 1170 个键指针对。 在一个 4 层的 B+ 树中，结构如下： 如果每个叶子节点存储 16 条记录（假设每条记录为 1KB），则总共可以存储约： 1170 × 1170 × 1170 × 16 ≈ 2.2 × 10^10 条记录。（
发布评论