从凌晨开始我就在盘今天这个打卡日：外卖项目要收尾，黑马点评短信登录的面经要整理，算法题里"树"这一章刷完了，图论正式开篇。0x3f打卡第38天，说充实是真充实，说累也是真累。我干脆按进度把它们分成三段来推进——项目、八股、算法都不耽误，这也是最近一个多月总结出来的节奏。
这篇记录一下今天是怎么收尾外卖项目、怎么梳理短信登录面经、怎么给树这个算法大类画句号，以及图论第一天我做了什么。如果你也走在Java后端这条学习路线上，或者正卡在"项目做完不知道接下来干什么"的节点上，这篇应该能给你一些参照。项目做完远远不是终点，怎么把项目里的经验变成自己的竞争力，才是真正拉开差距的地方。
1. 外卖项目第38天收尾：完结前我把核心链路重新跑了一遍
1.1 为什么代码写完了，我还坚持做一轮冒烟测试
我见过不少同学项目一完结，仓库一推就觉得万事大吉。我的习惯是：完结前一定把核心链路从头到尾手动走一遍，尤其是那些平时很少触碰的边界分支。外卖项目的核心链路其实很清晰：用户登录 → 浏览菜品 → 加入购物车 → 提交订单 → 支付 → 商家来单提醒 → 接单配送 → 完成订单。
这一轮走下来还真让我发现了问题。当时后台修改菜品之后，前台第一次查询已经命中了Redis缓存，用户看到的还是旧菜品信息。这个问题在开发阶段很少暴露，因为大家总在同一台机器上改完就跑前台，缓存还没到TTL就被手动清掉了。真正联调时，修改操作和查询操作分布在不同的请求链路里，缓存一致性问题就立刻现出原形。我的处理思路也不复杂：更新数据库之后主动删除对应缓存，等下一次查询再重建缓存。这套Cache Aside模式本身不复杂，难的是记住"删缓存而不是更新缓存"——更新缓存反而会让旧数据在并发窗口期被读到，删掉等重建反而更稳。
另外还复查了订单状态流转。订单从待付款到已付款再到配送中，每一步都该有状态约束，不能用裸update随便改。我最后用的是乐观锁的思路，在SQL更新时加上状态条件，update order set status = 2 where id = ? and status = 1，这样既能防止重复支付回调把状态改乱，也不至于引入复杂的锁机制。这里面的思想是：先检查前置状态是否符合预期，再执行更新，更新影响行数为0就说明状态已经变了，可以安全返回。
1.2 外卖项目真正值得写进简历的三个点
项目复盘到后面，我给自己定的标准是：能写进简历的亮点必须满足"技术选型有理由，实现方案可追问，出了问题有兜底"。按这个标准我筛出了三个。
第一个是Redis缓存菜品数据。这个点面试官基本都会深挖缓存穿透、缓存击穿、缓存雪崩。我在项目里至少做了一级防护，比如查不到数据时缓存空值来防止穿透，热点key设置逻辑过期时间防止击穿。问到一致性时，就回到Cache Aside模式，核心是"更新数据库后删缓存，让缓存自愈"。
第二个是WebSocket实时来单提醒。商家端需要第一时间感知新订单，HTTP轮询要么不及时要么费资源，所以我用WebSocket建立长连接，订单创建后由服务端主动推送。追问点通常是"WebSocket和HTTP的区别""连接断了怎么办"，我当时的处理是加心跳机制和断线重连。回答这类问题时不要只背概念，最好能说出你项目里心跳间隔怎么配置、断线后消息是否要做补偿推送。
第三个是支付回调的幂等设计。微信支付回调可能因为网络原因发送多次，如果每次回调都直接改订单状态，就会出现重复支付或状态错乱。我的做法是以订单状态作为更新条件，更新影响行数为0时说明已经处理过，直接忽略。这个设计在面试时很加分，因为只有真正处理过回调乱序问题的人才能讲出这种细节。
简历上不要写"我完成了订单模块"，而要写成"设计并实现了基于状态功能的订单状态流转方案，通过乐观锁解决支付回调的幂等性问题，避免重复通知导致的数据错乱"。核心是体现"解决了一个真实存在的问题"，而不是罗列功能列表。
1.3 完结后我顺手做了三件容易忽略的小事
第一件事是把项目用的SQL脚本、postman接口集合、核心配置说明整理成一个docs目录。别看这些琐碎，过两个月想再跑起来演示，没有这几样东西会非常痛苦。我当时就把初始化SQL直接放在项目根目录的sql文件夹下，还在README里写了启动步骤，包括Redis要开、MySQL要导入哪个脚本、短信验证码是模拟的等。
第二件事是把测试数据梳理了一遍，尤其是用户、订单、菜品这些有业务关联的数据。之前为了测试随意造的数据，有的手机号是乱写的，有的订单金额是负数，虽然不影响功能，但真要拿出去演示或者截图写博客，看着非常不专业。我花了一个小时把脏数据清掉，补了一批看起来正常的业务数据。
第三件事是给项目写了完整的README，内容包括项目背景、技术栈、模块划分、核心接口说明。很多面试官会直接打开你的GitHub看项目，没有README的项目哪怕代码写得再好，也显得不够专业。README不要写废话，要让看的人十分钟内知道这个项目是干什么的、怎么跑起来、结构长什么样。
2. 黑马点评短信登录：这份面经我按"会做且会说"的标准整理
2.1 短信登录完整链路：很多人一细说就暴露短板
黑马点评的短信登录是Redis应用里非常典型的场景。我直接按面试时的讲述顺序把链路过一遍，这条链路你如果能不看笔记复述出来，才算是真的掌握了。
第一步，前端输入手机号，后端先做格式校验。正则写成^1[3-9]\d{9}$基本够用，但你要能解释它的局限：它假设了11位数字、第一位是1、第二位是3到9，实际上不同运营商号段在演进，正规业务里还要考虑格式化、国际区号等问题。
第二步，生成6位随机验证码，把验证码存到Redis。Key的设计是login:code:{phone}，Value是验证码，同时设置TTL为5分钟。注意这里不能把验证码放到Session里，因为Session在分布式环境下天生不适合共享，Redis才是正确的选择。Redis自带过期能力，天然适合这种"临时凭证"场景。
第三步，调用短信服务商接口发送验证码。黑马点评在这个环节一般用模拟实现打日志，但面试中你要说明真实短信服务的成本点和风险点，比如频率限制、签名审核、模板审核、短信通道的到达率。
第四步，用户录入验证码后提交。后端从Redis取出验证码和用户输入做比对。比对成功后这一步通常还要做一件事：删除或标记这个验证码，避免同一个验证码被反复尝试。很多人在这一步偷懒，导致验证码可以被多次提交，这在面试官看来是安全意识不足。
第五步，根据手机号查询用户表。如果用户不存在，就自动创建一条用户记录，实现注册和登录的一体化。黑马点评里会为新用户初始化默认昵称和头像。这个"注册登录一体化"是业务上的经典设计，值得在面试中主动提一句。
第六步，生成一个UUID作为token，把用户信息以token为key写入Redis，TTL设置为30分钟。Value建议放UserDTO，只包含id、昵称、头像这些核心字段，别把手机号、密码这类敏感信息也塞进去。
第七步，把token返回给前端，前端后续请求在请求头中携带token。
这套链路讲下来，面试官会觉得你是真的动手做过，而不是背过答案。尤其是"验证码用完要删掉""UserDTO脱敏"这两个细节，绝大多数只会背流程的人都想不到。
2.2 登录态校验：两个拦截器加ThreadLocal，把职责拆干净
黑马点评里登录态校验这块的设计相当经典。很多初学者想的是"我直接在一个拦截器里判断token，不存在就禁止访问"，这个想法没错，但如果一个系统里既有必须登录的接口，又有允许匿名访问的接口，就会遇到麻烦：匿名接口也需要刷新token有效期，但你不可能因为匿名请求没有token就直接把它拒了。
这个项目用的方案是拆成两个拦截器，各管一件事。
第一个拦截器拦截所有请求，职责只有一个：如果请求头里带着token，就去Redis查一下用户，查到就放进ThreadLocal，并顺手刷新token的过期时间。它无论有没有token都放行，不决定谁可以访问、谁不可以访问。这样做的好处是匿名接口和登录接口都能触发token续期，用户只要在30分钟内操作任意一个接口，登录状态就不会断。
第二个拦截器只拦截需要登录的路径，职责是判断ThreadLocal里有没有当前用户，没有就返回401。这样两个拦截器一个负责"刷新登录态"，一个负责"把关访问权限"，逻辑非常干净，扩展起来也容易。比如新增一个匿名接口，只要不匹配第二个拦截器的路径规则就行。
ThreadLocal在这里的作用是让同一个请求线程共享一份用户信息。SpringMVC处理一个请求时，拦截器、Controller、Service大部分都在同一个线程里，所以用ThreadLocal存取很自然。但我必须强调一个坑：请求结束后必须remove。Tomcat的工作线程是复用的，如果不清理，线程处理完A用户的请求后，再处理B用户的请求时，ThreadLocal里可能残留A用户的信息，造成串号。这是面试官最爱挖的坑之一。
2.3 面经里必须准备的三个追问点
第一个追问是token过期怎么续期。我的理解是每次有效请求都重新设置过期时间，用Redis的expire命令把TTL重置。这样用户只要在30分钟内有过操作，登录状态就一直有效；超过30分钟完全没操作，token就失效了，需要重新登录。如果要做"记住我"功能，可以把TTL调长，或者再发放一个长效refresh token，由客户端在token过期时自动用它换新token。
第二个追问是同一账号多端登录怎么处理。项目里现有的token设计是每次登录生成一个全新的UUID，所以天然支持手机和电脑同时在线。如果业务要求只能单端登录，通常有两种做法：登录时把该账号所有旧token删除，或者直接用账号ID作为token的Key，让新登录覆盖旧登录。这两种方案各自有取舍，第一种会导致所有端掉线，第二种只保留最新端。
第三个追问是用户信息安全。返回给前端的用户信息必须脱敏，黑马点评用UserDTO来隔离实体类和视图对象。另外验证码存储也有讲究，生产环境至少要做加密处理，不能明文存Redis。
2.4 我整理的五条短信登录高频问答
| 问题 | 回答要点 |
|---|---|
| 验证码为什么要存Redis，不存Session | Session在分布式下共享困难，Redis天然共享且自带过期能力 |
| 验证码有效期多久，怎么设置 | 一般5分钟，过短影响体验，过长有安全隐患，按业务调整 |
| 登录成功为什么要返回token而不是Cookie | 前后端分离架构下Cookie受跨域限制，token放请求头更灵活，服务端无状态易扩展 |
| 如何防止验证码被刷 | 加图形验证码、手机号频率限制、IP限流、单日最大发送次数，黑名单机制 |
| 用户主动退出登录怎么做 | 删除Redis中对应token，让登录态立即失效；客户端同时清理本地token |
这五条属于保底储备，真正理解还要靠把项目跑起来多调试几遍。每次调试都能发现一些细节，比如Redis里的数据在可视化工具里长什么样、过期后第一时间访问是否会报NPE，这些真实的体感是背答案换不来的。
3. 树算法正式完结：我把这一章的套路提炼成了骨架
3.1 二叉树遍历四件套：递归、迭代、层序，一条模板记忆链
树这一章，我从二叉树遍历开始，而遍历又是所有树题的基础。递归版很简单，终止条件加单层逻辑；迭代版如果自己硬想，前序和后序还能凑合，中序很容易绕晕。我后来找到一套相对省脑子的模板：用栈存节点，用一个null标志位标记"下一个节点是待输出节点"。第一次碰到节点时不输出，先按逆序把右、左子树压栈，再压当前节点和null标记；弹出null时就输出栈顶节点。
拿前序遍历举例，最终我记住的模板是这样：
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); if (root != null) stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node != null) { if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); stack.push(node); stack.push(null); } else { res.add(stack.pop().val); } } return res; }中序和后序只需要调整压栈顺序，根本不用新背模板。这套标记法唯一的缺点是浪费一点空间，但换来的是心智负担大大降低。层序遍历则是另一套模板，用队列，每一轮先记录当前队列长度，然后按层输出，这个模板在"按层收集结果"的题里几乎原封不动地复用。
树类题目里最高频的题型其实就那几类：遍历输出、最大深度、翻转、对称、路径总和、最近公共祖先、二叉搜索树验证。绝大多数都可以基于遍历模板加少量递归逻辑解决。一道题如果卡住了，先问自己：它是需要"遍历过程中记录状态"，还是需要"从下往上汇总信息"，这两个方向基本决定了用DFS还是分治递归。
3.2 BST、AVL、红黑树：从"有序"到"平衡"的演进逻辑
二叉搜索树的核心性质是左小右大，中序遍历结果有序。验证BST时很多人会犯一个错：只判断当前节点大于左子节点、小于右子节点，这不够，因为可能出现左子树里某个节点比根节点还大的情况。正确做法是看中序遍历是否严格递增，或者在递归的时候维护一个上下界，把当前节点的值作为左子树的上界和右子树的下界传下去。
BST最怕有序插入，比如依次插入1到7就会退化成链表，查找复杂度从O(logn)变成O(n)。为了解决这个问题，才有了平衡树。AVL树定义平衡因子的概念，插入或删除后如果某节点左右子树高度差超过1，就通过LL、RR、LR、RL四种旋转重新平衡。AVL平衡非常严格，查询很快，但插入删除的旋转次数多，写起来也繁琐。
红黑树是工程界更常用的选择，Java里的TreeMap、TreeSet、以及HashMap在链表长度超过8时转成红黑树，都用它。红黑树的约束核心是保证最长路径不超过最短路径的两倍，相比AVL，平衡条件更松，插入最多两次旋转、删除最多三次旋转，综合维护成本更低。作为Java后端，二叉树和红黑树的面试概率很高，算法题层面你要能做到理解性质、说清和AVL的取舍，这比手写红黑树要现实得多。
3.3 树的另外几种形态：字典树、并查集、哈夫曼树
树这一章可不只有二叉树。这个月把二叉树刷完后，我又把字典树、并查集、哈夫曼树都过了一遍，它们都是"树"在不同场景里的变形。
字典树也叫前缀树，适合处理前缀匹配和词频统计。每个节点用长度为26的数组或Map存子节点，再加一个isEnd标记表示是否是一个完整单词。经典题像"实现Trie""最长公共前缀""单词搜索"。这套题型的难点在数据结构的定义和空间优化上，逻辑本身很固定。
并查集严格来说更像"森林"，用于处理联通性判断。核心操作只有两个：find找根、union合并。优化手段是路径压缩和按秩合并。代码非常短但用途极广，从无向图判环到冗余连接都能用。我写的模板大致是这样：
class UnionFind { int[] parent, rank; UnionFind(int n) { parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; } int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } void union(int a, int b) { int ra = find(a), rb = find(b); if (ra == rb) return; if (rank[ra] < rank[rb]) parent[ra] = rb; else if (rank[ra] > rank[rb]) parent[rb] = ra; else { parent[rb] = ra; rank[ra]++; } } }哈夫曼树则是带权路径长度最小的二叉树，构造过程是每次从集合中选两个权值最小的节点合并成一个新节点。面试和考试里常见的是计算WPL，也就是把所有叶子节点的权值乘以路径深度再求和。注意构造过程和WPL计算经常连在一起考，算法本身也不复杂，用优先队列模拟即可。
另外提一嘴，很多人搜"stm32时钟树""petalinux设备树"这类词时会把概念弄混，那只是"树"这个字在不同领域的不同含义。硬件里的设备树、时钟树是描述资源拓扑的数据结构，算法里的树是数据结构的基本形态。先把算法里的树学扎实，再看工程里的各种"树"，会顺畅很多。
3.4 我给"树完结"定的标准：题型闭环而不是题量堆积
很多人刷题喜欢卡数量，我更看重题型闭环。树这一章我对自己的标准是：看到题目先归类——属于遍历、属性计算、树的重建、搜索树相关、公共祖先，还是树的变形——然后立刻能掏出对应的解题骨架。到了这个程度，哪怕遇到没做过的题，也知道该往哪个方向想。
我刷完这章后统计了一下，LeetCode上二叉树和树相关题目大概刷了40道，包括翻转二叉树、验证二叉搜索树、二叉树的最大深度、最近公共祖先、从前序与中序遍历序列构造二叉树等高频题。数量不是重点，重点是把每道题背后的模板和变式吃透。比如"从前序和中序遍历构造二叉树"这道题，理解了切割区间的递归思路后，"从中序和后序构造"也就是改一行的事。
4. 图论开篇：第38天，正式开始碰"自由的连接"
4.1 从树到图，其实只差两点
树学完直接进入图论，在算法学习路径上非常自然。从数学定义上讲，树是连通且无环的无向图，所以图比树多出来的东西就两点：环和多连通分量。
图本身分有向图和无向图，也分带权图和不带权图。带权图在后续最短路径算法里会遇到，有向图则跟拓扑排序、强连通分量紧密相关。图论的经典问题大概归成几类：图的遍历、最短路径、最小生成树、拓扑排序、连通性问题、欧拉路径和匹配问题。每一类都有对应的经典算法，刷起来比树更有体系。
很多教材一上来就讲图的定义、完全图、简单图这些概念，容易把人劝退。我的建议是先把树里学到的DFS、BFS迁移过来。图的遍历就是树遍历的泛化，唯一区别是多了一个visited数组来防止走回头路。树里没有环，所以不用标记访问；图里有环，不标记就会死循环。
4.2 图的存储：邻接矩阵、邻接表、链式前向星怎么选
图的第一道选择题就是怎么存图。三种常见方案各有适用场景。
邻接矩阵用二维数组表示，判断两个点之间是否有边是O(1)，很直观，但空间是n的平方，10000个点就有些吃力了。适合稠密图、点数少的场景。
邻接表是工程和面试中最常用的方案，每个点维护一个列表，列表里存它能够到达的邻居。空间是O(n+m)，适合绝大多数的稀疏图场景，写起来也简单。用List<List<Integer>>或者List<int[]>[]就能实现。
链式前向星本质上是用数组模拟链表，性能更高，是竞赛圈的老朋友。Java写起来稍微啰嗦，但如果你以后要打算法竞赛，还是值得掌握。它把每条边存成结构体数组，用head数组记录每个点的第一条边，再用next指针串联同一起点的边。
| 存储方式 | 空间复杂度 | 判断边是否存在 | 适用场景 |
|---|---|---|---|
| 邻接矩阵 | O(n^2) | O(1) | 稠密图、点数少 |
| 邻接表 | O(n+m) | O(度) | 稀疏图、面试笔试常用 |
| 链式前向星 | O(n+m) | O(度) | 竞赛、追求极致性能 |
以我刷题的经验，多数笔试场景用邻接表就够了。需要对每条边带额外信息时，可以用List<int[]>这种轻量结构，把边权放在数组里。
4.3 今天跑通的第一道图论模板：BFS遍历一张无向图
图论第一天我不贪多，先写了建图和BFS遍历的模板。以最常见的无向无权图为例，给定n个点和m条边，从1号点出发按BFS顺序输出能访问到的所有节点。我默认编号从1开始，所以数组下标处理要留意。
public static void bfs(List<List<Integer>> graph, int n, int start) { boolean[] visited = new boolean[n + 1]; Deque<Integer> queue = new ArrayDeque<>(); queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int u = queue.poll(); System.out.print(u + " "); for (int v : graph.get(u)) { if (!visited[v]) { visited[v] = true; queue.offer(v); } } } }这个模板和树的层序遍历几乎一模一样，区别就是加了visited数组，因为图里可能有环。不标记visited的话BFS可能陷入死循环。DFS同理，只是把队列换成栈或者直接递归，核心套路完全一致。第一次跑通这个模板的时候，我明显感到树和图之间那层窗户纸被捅破了——原来树只是图的一种特殊情况。
然后我又顺手试了一下带权图的建法，其实就是把邻接表里存的元素从int变成一个包含目标点和权值的小对象，或者用int[]数组存两个值。后续Dijkstra的优先队列版本就是在BFS模板上把普通队列换成按距离排序的优先队列，思路的连贯性非常好。
4.4 0x3f3f3f3f：图论里马上要碰到的"无穷大"
标题里的0x3f，估计不少读者也好奇。0x3f3f3f3f是算法界常用的无穷大常量，十进制是1061109567，约10亿。
这个数用得很广，至少有三个理由。第一，它足够大，作为距离的初始值，不会被正常的边权干扰；第二，两个0x3f3f3f3f相加等于2122219134，仍然小于int的上限2147483647，所以不需要担心溢出成负数；第三，在C++里memset可以按字节填充，memset(dis, 0x3f, sizeof(dis))这一行就能把整个int数组初始化为0x3f3f3f3f，非常方便。
接下来的Dijkstra最短路、Floyd多源最短路，初始化dis数组时基本都会用到它。这算是算法圈的一种默契。我选择拿它当每天的打卡前缀，也算是对这段刷题时光的一种标记。
5. 第38天结束后，一些实在话
今天这一整天的节奏，其实是最近一个多月的一个缩影：白天补项目，晚上整理面经，再抽时间刷算法，三线并行。很多人会焦虑"我是不是进度太慢了"，我自己的体会是，刷题打卡的意义不在于和别人拼天数，而在于让每天都有一个最小可交付的进步。第38天，目标拆成三块，每块都完成了，这就够了。
最后分享一个我亲测有效的习惯：准备一个"卡壳记录本"。每次做题卡住超过20分钟，就记下卡在哪个概念、哪一步没想通，过几天再翻一遍。这比反复刷新题有用得多。树能顺利完结，很大程度是靠这个本子把以前总忘的东西钉牢了。
明天图论的部分，我给自己排了两个任务：拓扑排序和朴素Dijkstra。计划是先把模板写熟，再用三四道题巩固。这条路还长，但也正因为长，才值得一天一天走下去。
