Dai Wei

复杂度分析回答的不是「程序跑几秒」，而是「输入规模 n 变大时，资源消耗按什么趋势增长」。大 O 给出增长的上界刻度，均摊分析解释动态数组这类偶尔昂贵的操作为何仍算便宜，最好/最坏/平均则刻画同一算法在不同输入下的差异。 它解决什么问题真实运行时间被机器、语言、缓存、数据分布层层包裹，没有可比性。复杂度分析剥离实现细节，只保留「随 n 增长的趋势」这把与机器无关的尺子：动手前用它估算可行性（n 到 10^5 时 O(n²) 约百亿次操作，必然超时），讨论方案时用它统一「快」与「慢」的语义。 核心原理大 O 是渐进上界f(n) = O(g(n)) 的严格含义是：存在正常数 c 和 n₀，当 n 充分大之后恒有 f(n) ≤ c·g(n)。这个定义直接推出两条化简规则：常数因子可忽略，因为 c 本来就是任意的；低阶项可忽略，因为 n 足够大后高阶项必然主导。所以 3n + 20 记作 O(n)，n²/2 + 100n 记作 O(n²)。 与大 O 并列的还有 Ω（下界）和 Θ（夹紧的精确阶）。日常说「算法是 O(n log n)」时多半实际指 Θ，这...

二分查找的思想人人会讲——每次排除一半，O(log n)。真正拉开差距的是边界：left、right、循环条件、mid 更新，任何一处语义含糊就会死循环或漏答案。用循环不变量把区间语义钉死之后，所有变形都能推导，而不必背诵。 它解决什么问题在 n 个候选中定位目标，线性扫描 O(n)，二分每比较一次淘汰一半，只要 O(log n)——十亿规模约 30 次比较。成立的前提不是「数组有序」这个表象，而是单调性：一次判断能把候选切成「必不含答案」与「可能含答案」两半。有序数组只是特例，答案二分与旋转数组同样满足。 核心原理：循环不变量把二分写对的可靠方法是维护一条不变量：每轮结束时，答案（若存在）仍在当前区间内。围绕它做三件事：初始化覆盖全部候选；每轮据 mid 排除不可能的一半；区间每轮至少缩小 1 保证终止。循环条件、边界更新、返回值都是其推论。 写法一：左闭右闭 [left, right]两端都算候选，故 right 初始化为 n - 1；left == right 时还剩一个元素没查，所以循环条件是 left <= right；mid 被排除后从 mid ± 1 续搜...

LinkedList 是 JDK 中唯一的链表实现：它同时实现 List 与 Deque，头尾插删 O(1)，随机访问却只能折半遍历。读懂它的 Node 设计与 node() 定位逻辑，再对照 ArrayList 的连续内存模型，就能理解为什么官方作者都很少用它——「链表插入快」是个被过度传播的误解。 它解决什么问题链表的经典卖点是「插入删除不用搬移元素」：改动只涉及相邻节点的指针重连，与列表长度无关。LinkedList 把这个数据结构搬进集合框架，并顺手实现了 Deque 接口，让它可以同时扮演列表、队列、双端队列、栈四种角色。 但要清醒：链表免除的是「搬移」，不是「定位」。在指定下标插入前，仍然要先走到那个下标——这一步在链表上是 O(n) 的逐节点跳转，而 ArrayList 的搬移是连续内存上的批量拷贝。两种 O(n) 的常数天差地别，这是后面对比的关键。 核心原理public class LinkedList<E> extends AbstractSequentialList<E> implements List...

LinkedHashMap 是模板方法模式在 JDK 中的教科书级应用：它几乎不重写 HashMap 的增删查逻辑，只靠 Entry 多挂两个指针、再实现 HashMap 预留的三个空钩子，就让一个无序哈希表同时拥有了插入序、访问序和 LRU 淘汰能力。 它解决什么问题HashMap 的迭代顺序由哈希桶的物理分布决定，既不按插入先后，也不随访问变化，而且扩容后还会重排。很多场景恰恰需要顺序：配置项希望按录入顺序输出，日志聚合希望按出现次序遍历，缓存希望按「最久未使用」淘汰。这些需求的共同点是需要一条贯穿所有条目的逻辑次序。 朴素的方案是 HashMap 外面再套一个 List 记顺序，但两个结构要手工保持同步，删除时还要在 List 里 O(n) 查找。LinkedHashMap 的答案是：让节点本身就生活在两个结构里——哈希桶负责 O(1) 查找，一条额外的双向链表负责维护次序，二者共用同一份节点，任何修改都同步发生。 核心原理LinkedHashMap 继承 HashMap，哈希表的全部机制（位运算寻址、拉链、树化、扩容）原样复用。它叠加的东西只有三样： 双向链表：字段...

HashMap 是 JDK 集合体系中最重要的哈希表实现：JDK 8 采用数组 + 链表 + 红黑树的组合结构，用一次位运算定位桶，用扰动函数摊平碰撞，用 2 倍扩容和拆分重映射控制迁移成本。读懂它，就拿到了理解 ConcurrentHashMap 与各类缓存实现的钥匙。 它解决什么问题Map 的本质需求是「按 key 快速查到 value」。顺序表查找是 O(n)，二分是 O(log n)，而哈希表把 key 映射为数组下标，理想情况下一次定位，平均 O(1)。代价是哈希冲突不可避免：不同 key 可能算出同一个下标。HashMap 用拉链法承接冲突——数组的每个桶挂着一条链表，冲突元素依次链在后面。 在 JDK 集合家族里，HashMap 是 Map 接口的默认答案：它放弃线程安全和遍历顺序，换取单线程下极致的读写性能。Hashtable、ConcurrentHashMap、LinkedHashMap 都可以看作在 HashMap 这颗「性能内核」上叠加不同约束的产物。因此 HashMap 的源码是每个 Java 工程师绕不开的基本功。 核心原理JDK 7 的 HashM...

DelayQueue 是 JUC 中唯一的延迟阻塞队列：元素必须实现 Delayed 接口，只有剩余到期时间归零后才允许被取走。它用 PriorityQueue 按到期时间排序，用 leader-follower 模式把定时醒来的线程压到只有一个，是订单超时关闭、缓存过期这类单机延迟调度的标准答案。 它解决什么问题「N 分钟后做一件事」是业务高频需求：下单 15 分钟未支付自动关闭、缓存条目到期清理、会话超时剔除。朴素做法要么为每个任务开定时器、让线程 sleep，任务一多线程爆炸；要么起个线程轮询扫描全量任务，白白烧 CPU。理想的结构是一个按到期时间自动排序的队列：消费者永远只关心队头那个最近到期的元素，没到期就精确睡眠对应时长。DelayQueue 就是这个结构——它是无界阻塞队列，但「阻塞」的语义不是队列满，而是队头元素还没到期。 核心原理Delayed 契约入队元素必须实现 Delayed 接口，它只定义一个方法，同时继承了 Comparable： public interface Delayed extends Comparable<Delayed> ...

CopyOnWriteArrayList 是 JUC 中唯一的线程安全 List 实现，思路极为激进：读操作完全无锁，写操作先加锁再整体复制底层数组，改完把引用一次性换掉。它用写时复制换来了读的极致性能，也把适用范围严格限定在「读远多于写」的场景里。 它解决什么问题JDK 1.5 之前想要一个线程安全的 List，只有两条路：Vector，或者 Collections.synchronizedList 的包装器。两者的本质相同——在互斥锁上串行化所有方法，读读都互斥。而大量真实业务的特征是读操作数量碾压写操作：事件监听器列表、配置项、路由表，可能几天才改一次，但每秒被读几万次。给这样的场景配一把读写互斥的大锁，纯属浪费。 读写锁（ReentrantReadWriteLock）把读读放开了，但写和读仍然互斥，写发生时读要等待。CopyOnWriteArrayList 更进一步：读不加锁，写也不阻塞读，只有写写互斥。代价是写的时候复制整个数组——这就是名字里 Copy-On-Write 的含义，也是它一切优点与缺点的根源。 核心原理类的全部家当只有两样： public class...

ConcurrentHashMap 是 Java 并发编程中使用频率最高的线程安全 Map。JDK 8 用「CAS + synchronized 锁桶头」替换了 JDK 7 的 Segment 分段锁，配合多线程协作扩容和分段计数，把锁的粒度压缩到了单个桶。本文以 JDK 8 源码为主线，顺带讲清 JDK 7 方案被放弃的原因。 它解决什么问题HashMap 很快，但线程不安全：并发 put 会互相覆盖丢数据，size 的复合更新会丢失计数，JDK 7 的扩容甚至可能把链表接成环。最直接的补救是 Hashtable——所有方法挂 synchronized，读写都串行，相当于一张表一把大锁，并发度恒为 1。 真正的问题是：能不能让「不同桶」的写操作互不阻塞、让读操作彻底无锁？ConcurrentHashMap 就是对这个问题的两次回答。JDK 7 的回答是分段锁，JDK 8 的回答是 CAS 加桶级锁，后者在并发度、内存开销和代码结构上都更优，也成为今天分析的重点。 核心原理JDK 7：Segment 分段锁。 一个 ConcurrentHashMap 由一个固定长度的 Seg...

ArrayList 是整个集合框架中使用频率最高的类：底层只有一个 Object 数组，却通过懒初始化、1.5 倍扩容、批量拷贝把「动态数组」做得足够高效。读懂它的 grow、modCount 和 subList，就能解释日常开发里一大半诡异的并发修改异常和视图联动问题。 它解决什么问题Java 数组一旦创建长度就固定，而业务里的列表长度几乎总是未知的。ArrayList 在普通数组外面包了一层「容量管理」：对外暴露 size（元素个数），对内维护 elementData.length（数组容量），当 size 逼近容量时自动扩容。它要回答的核心问题是两个：怎么让随机访问保持 O(1)，又怎么让追加元素的均摊成本也是 O(1)。前者靠数组的内存连续性天然成立，后者靠「每次扩容按倍数放大，而不是一次加一个」来保证。 理解 ArrayList 的价值不只在用它，更在于它是 fail-fast 迭代器、视图（view）设计、数组拷贝这些 JDK 通用模式最干净的样本。 核心原理public class ArrayList<E> extends AbstractList&...

ArrayBlockingQueue 是 JUC 中结构最经典的有界阻塞队列：一块定长数组、一把 ReentrantLock、两个 Condition，就构成了完整的生产者-消费者模型。它的价值不在复杂，而在于用极简的结构把「队满阻塞生产者、队空阻塞消费者」做到线程安全且内存可控。 它解决什么问题生产者与消费者速度不匹配是多线程协作的常态。如果让双方直接交互，缓冲、等待、唤醒、背压都要自己处理，代码脆弱且易错。阻塞队列把「缓冲区 + 线程协调」封装成容器：生产者调用 put，队列满了就挂起等待；消费者调用 take，队列空了就挂起等待，双方只面向队列编程。ArrayBlockingQueue 是这个抽象下最朴素的实现：数组有界、内存可预估，天然适合作为线程池这类资源受限组件的缓冲层。 核心原理环形数组存储结构是定长的 Object[] items，配合三个游标：putIndex 指向下一次入队位置，takeIndex 指向下一次出队位置，count 记录元素个数。putIndex 自增到数组末尾时回绕到 0，takeIndex 同理，数组在逻辑上首尾相接成一个环。出队腾出的槽...