二叉树与二叉搜索树：递归遍历三板斧
线性结构（数组、链表）的局限在于：它们只有”一维”的先后关系。 但很多现实问题天然是”层次”的——目录结构、组织架构、表达式、决策过程。这时候就需要树。 而二叉树，是所有树结构里最基础、也最重要的一种。 什么是二叉树二叉树：每个节点最多有两个子节点（左子节点和右子节点）。 几个必须记住的术语： 根节点：最顶层的节点 叶子节点：没有子节点的节点 深度：从根到该节点的边数 高度：从该节点到最远叶子的边数 递归遍历三板斧处理树的几乎所有问题，都离不开遍历。二叉树有三种经典的深度优先遍历，区别只在于访问根节点的时机： 1234567891011121314151617181920212223// 前序遍历：根 → 左 → 右void preorder(TreeNode node) { if (node == null) return; visit(node); // 先访问根 preorder(node.left); preorder(node.right);}// 中序遍历：左 → 根 → 右void inorder(T...
哈希表：为什么它能做到 O(1)
哈希表（Hash Table）可能是日常写代码里用得最多的数据结构：Java 的 HashMap、Go 的 map、Python 的 dict，本质上都是它。 它的核心卖点是：增删查平均都是 O(1)。 但”为什么是 O(1)”，恰恰是最多人答不清楚的地方。今天把它彻底搞懂。 哈希表的本质：数组 + 哈希函数哈希表底层是一块数组。数组按下标访问是 O(1)，这是它快的根本原因。 问题在于：现实中的 key 通常不是整数下标（比如”用户 ID 是字符串”），怎么把一个任意的 key 映射成数组下标？ 答案是哈希函数： 1hash(key) → 数组下标 理想情况下，不同的 key 映射到不同的下标，那增删查就都是 O(1)。 但理想情况几乎不可能——因为 key 的取值空间通常远大于数组的大小，所以必然出现哈希冲突：两个不同的 key，算出了同一个下标。 冲突怎么解决解决哈希冲突有两种主流思路： 1. 链地址法（拉链法）同一个下标上挂一条链表，冲突的 key 都放在这条链表里。 查找时：先算哈希找到下标，再在链表里逐个比对 key。 Java 的 HashMap 用的就是这种方法...
数组、链表、栈、队列：最基础也最容易被问倒
很多人在面试里栽跟头，不是栽在什么高深的算法上，而是栽在最基础的线性结构上。 比如被问一句”数组和链表的区别是什么”，能说出”数组连续、链表不连续”的人很多，但能讲清楚”为什么数组按下标访问是 O(1)、链表在中间插入是 O(1)”的人，就少多了。 这篇文章把这四种最基础的线性结构，从底层特性到复杂度一次讲透。 数组：连续内存，随机访问数组的本质是一块连续的内存。 正因为连续，所以当你知道首地址和元素下标时，可以直接算出目标元素的地址： 1目标地址 = 首地址 + 下标 × 元素大小 这个计算是常量时间的，所以数组按下标访问是 O(1)，这就是”随机访问”。 但也正因为连续，数组有两个代价： 插入和删除要搬移数据：在中间插入一个元素，后面的元素都要往后挪一位，平均 O(n) 扩容成本高：数组创建时要指定大小，满了就得申请更大的新数组、整体拷贝 数组的适用场景：读多写少、大小相对固定。 链表：离散内存，靠指针连接链表的本质是每个节点存数据和下一个节点的指针，节点之间靠指针串联，不需要连续内存。 优点：插入删除快（只需改指针，O(1)），天然支持动态扩容 缺点：不能随机访问，...
策略模式与观察者模式：从 if-else 地狱里爬出来
如果说创建型模式解决的是”怎么 new 对象”，那行为型模式解决的就是”对象之间怎么协作”。 策略模式和观察者模式，是行为型模式里最常用、也最能立刻改善你代码质量的两个。 策略模式：消灭 if-else 地狱先看一段真实的坏代码。假设你在写电商的优惠券系统，有满减、折扣、立减三种优惠： 1234567891011public double calcPrice(String type, double price) { if ("fullReduction".equals(type)) { return price - 100; } else if ("discount".equals(type)) { return price * 0.8; } else if ("directReduction".equals(type)) { return price - 30; } else ...
从单体架构迁移到微服务，我是怎么设计的
从单体架构迁移到微服务，我是怎么设计的 架构演进从来不是”重写”，而是一场有节奏、可回滚、能持续交付的工程。本文复盘我在一个传统单体系统上做微服务化改造的完整设计思路。 为什么不直接重写接手时，系统是一个运行多年的单体应用，业务逻辑高度耦合，编译一次要十几分钟，任何小改动都要整体发版。团队第一反应是”推倒重写”。 但重写意味着：在很长一段时间内没有新功能产出，且新旧系统切换期的数据一致性几乎无法保证。最终我们选择了绞杀者模式（Strangler Fig Pattern）——在保留老系统运转的前提下，逐步把能力”绞杀”出来。 拆分原则：先按业务域，再按变更频率拆分粒度是最容易踩坑的地方。拆太细，分布式事务和运维成本爆炸；拆太粗，等于没拆。 我们的经验是两轮拆分： 第一轮按业务域：把系统切成若干个自治的领域边界（用户、订单、设备、GIS 等），每个域对应一个团队、一个独立的交付单元。 第二轮按变更频率：把”频繁变更”和”稳定不变”的模块再次分离，让高频模块能独立发布，不用拖着稳定模块一起回归。 判断边界是否合理的标准很简单：这个服务能不能独立演进、独立部署、独立扩容？ 如果三个...
工厂方法与抽象工厂：别再混为一谈
面试里经常出现这样的对话： “讲讲工厂模式。”“工厂模式有简单工厂、工厂方法、抽象工厂……” 然后就开始背定义。但背完往往自己也是糊的，因为这三个名字实在太像了。 其实它们的演进逻辑非常清晰，理清了就永远忘不掉。 起点：到处 new 的坏味道假设你在做一个支付系统，支持微信和支付宝两种支付方式。最初你可能会这么写： 12345if ("wechat".equals(type)) { return new WeChatPay();} else if ("alipay".equals(type)) { return new AliPay();} 问题来了：如果以后要加”银联支付”、”苹果支付”，这段 if-else 就得一直改，而且这样的判断散落在代码各处，改一处漏一处。 创建对象的逻辑，不应该和业务逻辑混在一起。这就是工厂模式要解决的问题。 第一站：简单工厂把创建逻辑抽到一个”工厂”里： 123456789public class PayFactory { public...
单例模式：饿汉、懒汉、双重检查锁，到底怎么选
单例模式大概是每个学 Java 的人第一个接触的设计模式，也是面试里被问烂、但很多人其实没真懂的一个。 它的目标很简单：保证一个类在整个系统中只有一个实例，并提供一个全局访问点。 为什么需要单例？典型场景：配置管理、线程池、数据库连接池、日志器、Spring 容器里的 Bean（默认就是单例）。这些对象如果重复创建，要么浪费资源，要么状态不一致。 难的不是”理解目标”，是在并发下正确、安全地实现它。 写法一：饿汉式123456789public class Singleton { private static final Singleton INSTANCE = new Singleton(); private Singleton() {} public static Singleton getInstance() { return INSTANCE; }} 类加载的时候就创建实例，所以叫”饿汉”——不管用不用，先造出来。 优点：简单，线程安全（由 JVM 类加载机制保证） 缺点...
设计模式入门：为什么需要它，以及三大分类
刚学设计模式的人，最容易犯一个错：把它当成”要背下来的 23 个名词”，然后拿着锤子到处找钉子。 这完全跑偏了。 设计模式的价值，从来不在”记住”，而在理解它为什么出现。 设计模式到底解决什么问题写代码久了你会发现，很多问题会反复出现： 怎么保证一个类只有一个实例？ 怎么在运行时切换不同的算法？ 怎么让两个模块解耦、互不直接依赖？ 怎么在不改老代码的前提下扩展新功能？ 这些问题被无数工程师踩过、想过、总结过，最后沉淀成了一套”常见问题的常见解法”——这就是设计模式。 它本质上是一套经验的复用。你不需要自己重新发明轮子，前人已经替你想好了。 把设计模式当”通用语言”我真正体会到设计模式的价值，是在团队协作里。 假设你在代码评审时看到这样一段话： “这里建议用策略模式把这块 if-else 拆掉。” 如果你们团队都懂策略模式，这句话一句话就说清楚了，不用解释一大堆背景。 但如果没人懂，你就得说：”你看这里，我们有三种计费方式，现在是 if-else 判断，以后可能还会加第四种、第五种，而且每个分支的逻辑还很长……” 设计模式是工程师之间沟通问题的通用词汇表。它让”复杂的设计意...