一、 基础盘点了解哪些数据结构在深入对比之前我们先快速扫盲一下常见的数据结构这部分是基础。数组Array内存空间连续。因为连续所以支持随机访问时间复杂度是O(1)。适用于按索引访问元素的场景但插入和删除较慢时间复杂度O(n)因为可能需要移动后续元素。链表Linked List由节点组成节点之间分散存储内存不连续。每个节点存储数据和指向下一个节点的指针。适用于频繁插入和删除的场景但随机访问较慢。栈Stack一种后进先出LIFO的数据结构只允许在栈顶进行插入和删除操作想象一下叠盘子。队列Queue一种先进先出FIFO的数据结构允许在队尾插入元素在队首删除元素想象一下排队买奶茶。树Tree一种非线性数据结构由节点和边组成每个节点可以有多个子节点。适用于表示层次关系如文件系统、组织架构。 二、 高频考点数组和链表的区别到底是什么不要只回答“一个连续一个不连续”我们要从四个维度来降维打击1. 访问效率O(1) vs O(n)数组可以通过索引直接计算出内存地址直接访问任何位置的元素访问效率高时间复杂度为O(1)。链表需要从头节点开始遍历顺着指针挨个找到目标位置访问效率较低时间复杂度为O(n)。2. 插入和删除操作效率⚠️陷阱预警数组插入和删除操作可能需要移动其他元素时间复杂度为O(n)。链表⚠️ 划重点如果在已经持有目标节点引用的前提下链表只需要修改指针指向时间复杂度为O(1)。但是如果是要在“某个值”或“某个位置”做插入/删除仍然需要先从头遍历找到目标节点整体的查找时间依然是O(n)。所以不要一上来就说链表插入是O(1)一定要加上“已知前驱节点/持有引用”的前提3. 缓存命中率博主加餐底层原理拉开差距数组由于数组元素在内存中连续存储根据计算机的空间局部性原理CPU读取某个元素时会将相邻的一整块内存都加载进CPU缓存Cache Line。因此数组可以极大提高CPU缓存的命中率链表节点在内存中是不连续存储的容易导致CPU缓存的命中率较低。频繁的缓存失效Cache Miss会严重影响性能。这也是为什么在实际开发中即使频繁增删很多时候ArrayList依然比LinkedList更快的原因。4. 应用场景总结数组适合静态大小、频繁访问元素的场景读多写少。链表适合动态大小、频繁插入/删除操作的场景写多读少。为了让大家更直观地记忆我整理了一个表格维度数组 (Array)链表 (Linked List)内存分配连续内存空间离散存储靠指针相连随机访问O(1) O(n)插入/删除 O(n)需移动元素O(1)⚠️需已知目标节点引用否则查找仍需O(n)缓存命中率高连续存储CPU缓存友好低内存离散易发生Cache Miss适用场景静态大小、频繁访问动态大小、频繁插入/删除三、队列和栈的区别是什么主要区别在于元素的插入和删除方式以及元素的访问顺序。插入和删除方式队列Queue采用先进先出FIFO的方式。新元素插入队尾入队删除操作发生在队首出队。栈Stack采用后进先出LIFO的方式。新元素插入栈顶进栈删除操作也发生在栈顶出栈。元素的访问顺序队列元素按照插入的顺序进行访问先插入的元素先被访问到。栈元素按照插入的逆序进行访问最后插入的元素先被访问到。典型应用场景队列适用于需要按照插入顺序进行处理的场景例如任务调度、消息队列。栈适用于需要维护最近操作状态的场景例如函数调用栈、浏览器的后退功能、括号匹配。四、☕ 介绍一下数据结构中的栈怎么用Java实现栈Stack是一种特殊的线性数据结构只能够在一端即栈顶进行插入和删除操作基本操作有加入数据push和输出数据pop两种。在Java中可以通过多种方式实现栈数组实现适合已知最大容量的情况但可能会因为容量限制导致栈溢出StackOverflow。链表实现动态大小没有溢出的问题但需要额外的内存来存储指针。内置Stack类简单易用适合一般情况。⚠️避坑但由于其继承自Vector所有方法都加了synchronized锁在多线程环境中可能不够高效。实际开发中通常推荐使用ArrayDeque来实现栈的功能。 算法题如何使用两个栈实现队列这是一道非常经典的算法题考察对这两种数据结构特性的理解。实现思路准备两个栈分别称为stackPush负责入队 和stackPop负责出队。入队时直接将元素压入stackPush栈。出队时先判断stackPop是否为空。如果不为空直接弹出stackPop的栈顶元素。如果为空则将stackPush中的所有元素依次弹出并压入stackPop中然后再从stackPop中弹出栈顶元素作为出队元素。查询队首元素时同样需要先将stackPush中的元素转移到stackPop中然后取出stackPop的栈顶元素但不弹出。通过上述方法可以实现用两个栈来模拟队列的先进先出FIFO特性。️ 常见的队列有哪些及应用场景除了基础的队列根据底层实现和业务需求的不同队列演化出了多个变种这也是面试中拉开差距的加分项顺序队列利用一组连续的存储单元依次存放从队头到队尾的元素同时设置两个指针队头指针 front、队尾指针 rear。痛点实现简单但空间利用率低。当队尾指针到达数组末尾时即使前面有空闲空间也可能无法继续插入元素造成“假溢出”。场景一些简单的、对队列操作不太频繁且数据量相对较小的场景如学校食堂打饭排队系统。链式队列通过链表来实现的队列每个节点包含数据域和指针域。队头指针指向链表头节点队尾指针指向链表尾节点。优势插入和删除操作在链表两端进行不需要移动元素操作效率高。可动态分配内存不存在空间溢出问题。但需要额外的指针空间来存储节点间的链接关系。场景常用于处理数据量不确定、需要频繁进行插入和删除操作的场景如操作系统中的进程调度。循环队列把顺序队列的存储空间想象成一个首尾相接的圆环。当队尾指针到达数组末尾时若数组头部还有空闲空间则将队尾指针重新指向数组头部。优势充分利用了数组的空间避免了顺序队列中的假溢出问题提高了空间利用率。痛点实现相对复杂需要处理队头和队尾指针在循环时的特殊情况通常需要牺牲一个存储单元或引入 size 变量来区分队空和队满。场景常用于数据缓冲区的管理如音视频数据的缓冲。双端队列Deque一种特殊的队列它允许在队列的两端进行插入和删除操作。既有队头指针又有队尾指针两端都可以作为队头或队尾进行操作。优势灵活性极高支持多种操作模式。场景在需要频繁在两端进行数据操作的场景中非常有用如浏览器的页面浏览历史记录新访问的页面可以从队头或队尾插入浏览过的页面可以从两端删除。优先级队列Priority Queue每个元素都有一个优先级在插入和删除元素时会根据元素的优先级来进行操作优先级高的元素先出队。底层实现通常使用堆Heap数据结构来实现以保证高效的插入和删除操作。能够快速获取优先级最高或最低的元素并进行处理。复杂度插入和删除操作的时间复杂度通常为 O(log n)其中 n 是队列中的元素个数。场景任务调度系统、操作系统中的进程调度实时性要求高的进程具有较高的优先级。五、⚖️ 平衡二叉树结构是怎么样的1. 为什么要有平衡二叉树大白话版普通的二叉搜索树BST有个致命缺点如果你按顺序插入 1、2、3、4、5它会直接退化成一条“链表”只有右孩子。查询的时间复杂度瞬间从理想的O(log n)变成了最坏的O(n)。这就好比本来你想用“二分查找”快速找人结果树长得太偏你只能顺着一条线挨个找。2. 什么是平衡二叉树为了不让它长歪我们引入了平衡树。所谓平衡树就是将二叉查找树平衡均匀地分布减少树的深度。⚠️避坑平衡二叉树首先必须是一棵二叉搜索树其次它的条件是左右两个子树的高度差平衡因子的绝对值不超过 1。左右两个子树也都是一棵平衡二叉树。六、 红黑树说一下跳表说一下1️⃣ 红黑树Red-Black Tree一种“弱平衡”的自平衡二叉查找树由于严格平衡的 AVL 树在插入删除时极其容易触发旋转为了兼顾性能红黑树诞生了。它不追求绝对的平衡而是追求“大致平衡”。红黑树的 5 大铁律每个节点非红即黑。根节点是黑色的。每个叶子节点NIL空节点都是黑色的。如果一个节点是红色的则它的两个子节点必须是黑色的不能红红相连。从任意节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点黑高相同。 大白话解释红黑树就像是通过给节点“穿红黑衣服”来管理平衡。只要有任意一条路径上黑节点数量不一致或者红节点挨着红节点了就需要通过左旋、右旋、变色来调整。这保证了最长路径不超过最短路径的两倍保证了最坏情况下操作的时间复杂度依然为O(logN)。2️⃣ 跳表Skip List给链表加个“快车道”链表查询很慢O(n)那怎么优化跳表给出了一个极其聪明、且实现简单的方案加索引。底层是一个普通的有序链表。上层建立多级索引每上一层都是下一层的子集。查数据时先在上面的大索引里大步跳跃类似坐高铁到了大致位置再钻进下一层换乘地铁最后到最底层步行。这样大大减少了搜索的时间复杂度平均搜索、插入、删除的时间复杂度都达到了O(log n)。 哪些地方用了红黑树和跳表epoll用了红黑树来保存监听的 socket。Redis用了跳表来实现 zset有序集合。为什么 Redis 不用红黑树而用跳表因为跳表实现更简单且在并发环境下做范围查询ZRANGE极其方便只需顺藤摸瓜即可。 红黑树和AVL树相比谁更好高频对比题这张图总结得非常好我们可以用“跑车 vs 越野车”来比喻维度AVL 树 (跑车)红黑树 (越野车)查询性能⭐⭐⭐⭐⭐严格平衡树更矮所以查询飞快⭐⭐⭐⭐弱平衡高度略高查询稍慢但也是 O(logN)插入/删除性能⭐⭐⭐极易破坏平衡需要频繁旋转开销大⭐⭐⭐⭐⭐变色最多两次旋转就能搞定效率极高平衡开销高严格维持绝对平衡低容忍局部不平衡 实际开发怎么选如果查多写少选 AVL 树比如数据库索引虽然实际上数据库多用B树。如果读写频繁选红黑树。语言级应用在 Java 中TreeMap和TreeSet底层清一色使用的是红黑树就是为了兼顾插入、删除和查询的综合性能。七、 二叉搜索树最坏的时间复杂度为什么会这样以及用什么解决1. 二叉搜索树BST的“致命伤”普通BST的查询时间复杂度是O(log n)但这仅仅是最理想的情况。想象一下你按顺序往树里插入 1、2、3、4、5。因为BST的规则是“小的放左边大的放右边”所以新插入的节点永远在右边。结果是什么这棵树直接退化成了一个单链表查询数据的时间复杂度瞬间从O(log n)崩坏到O(n)。2. 救星平衡二叉查找树AVL树为了不让它长歪大佬们提出了AVL树。它强行加了条件约束每个节点的左子树和右子树的高度差不能超过1。一旦插入元素导致高度差超过了1就会触发“左旋/右旋”来重新维持平衡。这样就能保证无论怎么插入查询时间复杂度始终维持在O(log n)。⚠️避坑注意AVL树是强平衡。虽然查询爽了但每次插入都可能疯狂旋转插入性能大打折扣这就引出了我们上一篇讲的红黑树弱平衡换取插入性能。八、️ B树的特点是什么MySQL为什么选它B树是一种自平衡的多路查找树。为什么数据库MySQL偏爱它因为它完美解决了磁盘I/O的问题。B树的核心特点通俗大白话版多路树树矮不是二叉的一个节点可以存多个键值对比如16kb一页。树越矮查数据时读磁盘的次数就越少。数据只存叶子目录与数据分离非叶子节点仅包含索引信息干活的就是目录不存储具体的记录数据。所有的数据记录都在最底层的叶子节点。注非叶子节点的“键数和子指针数”不同教材有差异经典教材n个键对应n1个子指针MySQL InnoDB里通常n个键对应n个子指针。叶子节点有链表查范围贼快所有叶子节点都在同一层且通过指针通常是双向链表相互链接。适合范围查找比如WHERE id 10。 B树和B树有什么不一样这两者经常被拉出来公开处刑。记住一句话B树是每个节点都存数据而B树把数据全塞到了最底层的叶子节点。B树与B树的三大区别检索路径B树可能在非叶子节点比如根节点就刚好找到目标数据直接返回路径长度不定。而B树必须一路走到叶子节点才能拿到数据路径长度是固定的意味着查任何数据耗时都很稳定。非叶子节点内容B树的非叶子节点既存索引又存数据导致一个节点存不了几个键树会变高。B树的非叶子节点只存索引一个节点能塞下几百上千个键层高极低极大减少了磁盘I/O。叶子节点结构B树的叶子节点各自独立查范围只能靠“中序遍历”来回回溯。B树的叶子节点是一个有序的双向链表找到开头顺着链表往后捞就行范围查询性能碾压B树。 终极对比红黑树、B树、B树有什么区别“为什么MySQL用B树而Java的TreeMap用红黑树”我们用一张表把它们的底裤扒干净特性红黑树B树B树节点容量每个节点存1个键值对二叉每个节点存多个键值对多路非叶节点存多个键仅叶节点存值数据存储位置所有节点均存数据所有节点均存数据数据仅存于叶子节点平衡维护方式颜色标记与旋转节点分裂/合并节点分裂/合并查找稳定性查到即返回查到即返回必须查至叶节点稳定O(log n) 核心区别查询效率与I/O红黑树是二叉树数据量1亿时树高约30层磁盘I/O次数多。B/B树是多路树相同数据量下树高可能仅为1/3比如3层显著减少磁盘I/O。范围查询B树的叶子节点是链表范围遍历效率极高。B树和红黑树则需要复杂的回溯或频繁调整指针。维护成本红黑树需频繁旋转变色。B/B树通过节点分裂合并更适合海量数据。 场景选择总结数据在内存中 高频增删 选红黑树比如Java的TreeMap、HashMap扩容后。数据在磁盘中 随机/范围查询 选B树比如MySQL的InnoDB索引。九、⛰️ 堆是什么1. 核心概念大白话堆Heap本质上是一棵完全二叉树通常用数组来存储所以也叫二叉堆。它分为两种大顶堆任何一个节点的值都大于等于其子节点的值。所以根节点是整棵树的最大值。小顶堆任何一个节点的值都小于等于其子节点的值。所以根节点是整棵树的最小值。看图区分图 1、2 是大顶堆图 3 是小顶堆。图 4 为什么不是堆不是因为数值大小错了而是因为它连完全二叉树都不是节点空缺导致结构断层。记住堆必须先是完全二叉树。3. 应用场景优先队列PriorityQueueJava中的PriorityQueue底层就是堆。Top K 问题求100亿个数中最大的10个用小顶堆求最小的10个用大顶堆。堆排序。十、 前缀树是什么有什么应用1. 核心概念大白话前缀树Trie Tree又叫字典树。它的核心思想极其简单利用字符串的公共前缀来减少查询时间最大限度减少无谓的字符串比较。2. 三大铁律根节点不包含字符。从根节点到某一节点路径上经过的字符连接起来就是该节点对应的字符串。每个节点的所有子节点包含的字符都不相同。3. 应用场景搜索引擎自动补全输入 app快速找出 apple, application。拼写检查判断单词是否存在。IP路由表匹配网络路由中根据IP地址的前缀选择合适路由最长前缀匹配效率极高。词频统计节点中记录单词出现次数。十一、 LRU是什么如何实现1. 核心概念大白话LRULeast Recently Used是一种缓存淘汰算法。当缓存空间满了优先淘汰最长时间未被访问的数据。2. 为什么是“哈希表双向链表”要自己手写一个LRU你必须回答出这个经典组合哈希表提供 O(1) 的查找能力通过 key 快速找到链表中的节点。双向链表提供 O(1) 的插入、删除和移动能力❓ 为什么不单纯用双向链表假设我们只维护一个双向链表不用哈希表。会发生什么访问get效率极低致命缺陷当你发起一个get(key)请求时你怎么知道这个key在不在链表里你只能从头节点开始顺着指针一个一个遍历去比对 key。这个查找过程的时间复杂度是O(n)。致命点缓存设计的初衷就是为了“快”如果每次读数据都要 O(n) 遍历那缓存不仅没加速反而比直接查数据库还慢。完全失去了使用缓存的意义。淘汰put时找不到目标缓存满了要淘汰数据我们需要删掉链表尾部最久未用的节点。因为有尾指针删尾节点确实是 O(1)。但是怎么判断新来的数据是不是已经在链表里还是需要 O(n) 遍历去查重。结论单纯用双向链表查找是 O(n)这不可接受。❓ 那为什么不单纯用哈希表假设我们只用HashMap没有双向链表。缺乏时间序无法淘汰HashMap 是无序的。当缓存满了我们需要淘汰“最久未访问”的那个数据。HashMap 里根本没有记录哪个数据是刚刚访问的哪个是一个月前访问的。你无法在 O(1) 的时间复杂度内找到那个“最老”的数据。无法快速腾挪即使你知道了要淘汰谁在HashMap里做删除操作如果不结合链表也无法高效维护其他元素的“新旧顺序”。结论单纯用哈希表淘汰是 O(n)且无法维护访问顺序。 完美组合哈希表 双向链表各司其职这就好比一个仓库双向链表和一个智能台账哈希表哈希表的作用O(1) 快速定位它只负责告诉你“你要找的货在仓库的哪个位置节点的指针”。双向链表的作用O(1) 移动与增删每次访问数据通过哈希表 O(1) 找到节点后因为它是双向的我们可以直接 O(1) 把这个节点从链表中拆下来扔到链表头部表示最近访问。缓存满了直接 O(1) 删掉链表尾部最久未访问的节点即可。⚠️ 延伸追问为什么是“双向”链表单链表差在哪既然已经有了哈希表帮我们 O(1) 找到节点链表的作用只剩“增删改”那单链表行不行不行必须是双向链表。因为我们要在 O(1) 的时间内把当前访问的节点移动到链表头部。如果用单链表我们知道了当前节点要把它从原来的位置“摘”下来。单链表只知道 next 指针不知道 prev 指针。要删除它必须从头遍历找到它的前驱节点这就又变成O(n)了。如果用双向链表通过node.prev和node.nextO(1) 时间就能把节点从中间抠出来再接到头部完全是常数级操作。 博主总结一句话“只用双向链表查找是 O(n)只用哈希表无法维护淘汰顺序。哈希表提供 O(1) 的快速查找能力双向链表提供 O(1) 的插入、删除和移动能力两者结合使得 LRU 的所有操作get 和 put都能在 O(1) 的时间复杂度内完成。”3. 实现步骤使用哈希表存储数据key - 节点指针。使用双向链表存储节点链表头部为最近访问的节点链表尾部为最久未访问的节点。访问数据时如果存在将对应节点移动到链表头部如果不存在新建节点放到头部。如果缓存满了直接删掉链表尾部的节点。所有操作的时间复杂度都是O(1)。十二、️ 布隆过滤器怎么设计时间复杂度1. 为什么需要它场景现在要给项目添加IP黑名单功能有1亿个恶意IP如何判断一个IP在不在黑名单中用 Java 的 HashMap1亿个IP要占用巨大内存直接OOM。我们只需要判断“存在与否”不需要存具体的值布隆过滤器就是为此而生的。2. 核心原理大白话它是一个很长的二进制向量位数组多个哈希函数。添加元素将元素通过 K 个哈希函数计算得到 K 个位置将这些位置全部置为 1。查询元素同样计算 K 个位置。如果所有位置都是 1则判定“可能存在”如果有任何一个位置是 0则判定“绝对不存在”。3. ⚠️ 核心特性与陷阱优点空间效率极高运行速度快时间复杂度 O(k)k是哈希函数个数。缺点存在误判率假阳性False Positive Probabilityfpp且无法删除元素为什么会有误判因为不同的元素可能哈希到相同的位置哈希碰撞。即使某个元素没被加入但可能其他元素把它的哈希位都置为了1导致误判。为什么无法删除因为多个元素共享位数组中的某些位如果直接置0会影响其他元素。调优提高数组长度或哈希函数个数可以降低误判率但会增加CPU和内存开销。fpp不能定义为100%因为无法100%保证不发生哈希碰撞。4. 经典应用场景缓存穿透保护Redis 前置布隆过滤器拦截不存在的请求。垃圾邮件过滤。爬虫URL去重。黑名单校验小结️ 数据结构全景图线性的基石顺序 vs 链式数组连续内存查的快O(1)增删慢O(n)。CPU缓存友好。链表离散存储查的慢O(n)增删快O(1)前提是已知节点引用。操作受限的线性表栈LIFO先进后出、函数调用、括号匹配、逆序处理。队列FIFO先进先出、任务调度、消息队列、层序遍历。还有循环队列、双端队列Deque、优先级队列堆实现。树与图的天下从二叉树到海量存储BST - AVL - 红黑树查询性能与平衡开销的博弈。Java中的TreeMap、HashMap底层的扩容树化用的就是红黑树弱平衡综合性能最优。B树 vs B树MySQL的宠儿。矮胖多路叶子节点链表相连完美适配磁盘I/O与范围查询。堆完全二叉树解决Top K问题的神器。大厂进阶利器场景驱动前缀树Trie搜索引擎自动补全IP路由匹配。跳表Skip ListRedis ZSet底层用空间换时间实现比红黑树简单。LRU哈希表双向链表O(1)查找 O(1)增删移缓存淘汰经典方案。布隆过滤器位数组多哈希解决缓存穿透绝对的“宁可错杀一千绝不放过一个”判定不存在则绝对不存在。 预告与互动下一篇我们将直接切入【算法篇】