复杂度 · 数据量估算 · 二分查找 · Top K · 小顶堆 · 滑动窗口 · TimSort · 双轴快排 · 稳定性 · 比较器约定 · 红黑树 · 旋转 · 变色 · 题型地图
数据结构与算法：先估量级，再按“怎么查”提前摆好数据
业务里的算法题，几乎都是同一个套路：先用数据量估一下 O(n²) 会不会爆，再把数据提前组织成“查起来便宜”的样子。按 key 找就放进哈希表，要最大的几个就维护一个小堆，要按范围查就先排好序再二分，要“最近一分钟”就用一个两头进出的队列当窗口。Java 的集合和 Arrays 已经把这些结构写好了，日常要做的是认出“这是哪一类问题”，挑对工具，再别踩比较器和边界的坑。红黑树是这些工具里最复杂的一个，本页手推一遍它的插入。
全景：一个订单对象的一生 · 第 4、9 站地图：J01 · 数据结构与算法（最后一个知识点）前面几页：集合怎么选 · HashMap · HashMap 的亲戚们实验：JDK 17.0.20 实测
①要解决的问题：交易靶场里冒出来的四道题
在全景第 9 站，这一步要解决的是：几十万个待付款订单里，每次只要“最早到期的那一个”。DelayQueue 底下的二叉堆就是为这类问题生的。同一个靶场里，类似的题还有好几道：运营要每天的热销 Top 10；客服要按时间段查订单；风控要同一个用户一分钟内最多下 5 单；财务的对账单要按金额排序，同金额的还得保持下单顺序。第 4 站的 HashMap 是第五道：按 key 一步找到。
| 靶场里的需求 | 其实是哪类题 | 用什么 | 在哪讲 |
|---|---|---|---|
| 第 4 站：按商品号找商品 | 按 key 查找 | 哈希表 HashMap | HashMap 页 |
| 第 9 站：最早到期的先取消 | 反复取最小 | 二叉堆 PriorityQueue | 集合怎么选④-5 |
| 热销 Top 10 | Top K | 大小为 K 的小顶堆 | 本页④-3 |
| 查 12:05～12:15 的订单 | 有序数据的范围查找 | 排序 + 二分，或 TreeMap（红黑树） | 本页④-2、⑤ |
| 一分钟内最多 5 单 | 滑动窗口 | 两头进出的队列 ArrayDeque | 本页④-4 |
| 对账单按金额排，同额保持时间序 | 稳定排序 | List.sort（TimSort） | 本页④-5 |
②朴素做法：每次都把数据从头看一遍
- Top 10 要的只是 10 个，全排序却把 100 万个都排好了：做了很多不需要的工作。Stream 版还要把 100 万个 int 装箱成 Integer。
- 时间戳本来就是有序的（订单按时间写入），从头扫等于没利用这条信息。
- 缺的那一块：只维护你需要的那部分顺序（堆只管最小的在顶上），利用数据已有的顺序（有序就二分）。
不懂精华时的典型误用：觉得“数据量才 1 万，随便写”，在循环里套循环（O(n²)，1 万的平方是 1 亿次），一个接口 2 秒；数据长到 10 万，就是 200 秒（④-1 估算）。
③几种思路：把数据摆成什么样
本页的重点：④讲五个关键洞察（量级估算、二分、Top K、滑动窗口、Java 的排序），⑤手推红黑树插入并用反射核对 TreeMap，⑥讲边界坑和面试题型地图。
④关键洞察
④-1先估量级：一台机器一秒大约做 1 亿～10 亿次简单操作
| 数据量 n | O(log n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|---|
| 1 千 | 10 | 1 千 | 1 万 | 100 万 |
| 1 万 | 14 | 1 万 | 14 万 | 1 亿 |
| 100 万 | 20 | 100 万 | 2000 万 | 1 万亿 |
| 1 亿 | 27 | 1 亿 | 27 亿 | 不可能 |
按“一秒 1 亿次”估：接口里 O(n²) 碰上 1 万条就是 1 秒；100 万条的 O(n log n) 排序是几十毫秒（实测 int[] 排序 77.6 ms）。这个表是用来做决定的：写代码前先问数据量会长到多大。
④-2二分：有序 + 每次砍掉一半，不变式是关键
- 1“找第一个 ≥ key 的位置”（lower bound）：在
[lo, hi)里找，不变式是“答案一直在 [lo, hi] 之间”；a[mid] < key说明答案在 mid 右边，lo = mid + 1；否则答案可能就是 mid，hi = mid；lo == hi时就是答案。 - 2时间段 [t1, t2) 的订单 = 下标
[lowerBound(t1), lowerBound(t2))。实测 100 万个时间戳，两次二分共比较 40 次，和从头扫 100 万次命中同样的 1621 单。 - 3二分写错的地方几乎都在边界：
hi是开区间还是闭区间、lo = mid会不会死循环、(lo + hi) / 2会不会溢出（⑥ 坑 3）。JDK 的Arrays.binarySearch找不到时返回-(插入点) - 1，也能拿来求插入点。
④-3Top K：只盯住“当前第 K 大”的门槛
- 1维护一个大小为 K 的小顶堆，堆顶就是“目前入选的 K 个里最小的那个”，也就是门槛。来一个新数：比门槛小，直接丢；比门槛大，挤掉堆顶，自己进去。
- 2复杂度 O(n log K)：K = 10 时 log K 约 3，基本就是扫一遍。实测 100 万单 3.3 ms，比全排序快 20 多倍。
- 3为什么找最大的 K 个要用小顶堆？因为每次要比较、要踢掉的，是入选者里最小的那个。反过来找最小的 K 个就用大顶堆（
new PriorityQueue<>(Comparator.reverseOrder())）。
④-4滑动窗口：只保留窗口里的数据，从一头进、另一头出
- 1“每个用户 60 秒内最多 5 单”：每个用户一个 ArrayDeque，存最近几次下单的时间。新请求来时，先把队头那些早于
now − 60s的扔掉，剩下的个数 ≥ 5 就拒绝，否则把 now 加到队尾。 - 2每个时间戳最多进一次、出一次，所以总代价是 O(n)，不用每次重新数 60 秒内有几单。
- 3实测 用户 1024 在第 0、5、10、20、30、40、55、61、66、125 秒下单：前 5 单放行，40、55 秒拒绝；61 秒时第 0 秒那单出了窗口，放行。这就是限流里的“滑动日志”算法；生产里多实例要共享计数，放进 Redis（J12 会讲令牌桶、漏桶）。
④-5Java 的排序：对象用 TimSort（稳定），基本类型用双轴快排
TimSortArrays.sort(Object[])、List.sort、Collections.sort
- 稳定：相等的元素保持原来的先后。实测 先按时间排、再按金额排，同金额的订单保持时间顺序
- 利用已有顺序：找出数据里本来就有序的片段（run），再合并；对“几乎有序”的数据接近 O(n)
- 最坏 O(n log n)，要额外 O(n) 的空间
- 依赖比较器遵守约定，否则可能抛 “Comparison method violates its general contract!”（实测，⑥ 坑 1）
双轴快排Arrays.sort(int[]、long[]、double[]…)
- 原地排序，不要额外空间，常数小，实际最快
- 两个基准把数组切成三段；小段改用插入排序（JDK 17 源码里还混合了堆排序兜底，防止退化）
- 不稳定：但对基本类型无所谓，两个 5 分不出谁是谁
⑤手推一遍：红黑树的插入，以及靶场里的四道题
TreeMap 能在边改边查的情况下一直保持 O(log n)，靠的是红黑树：插入后如果破坏了规则，就靠变色和旋转修回来，而且最多旋转两次。下面依次插入 10、20、30、15、25、5、1，每一步都和 JDK 17 TreeMap 用反射读出来的结构一致。
- 每个节点非红即黑，根是黑的，空节点算黑的。
- 红节点的孩子必须是黑的（不能连着两个红）。
- 从任一节点往下到每个空节点，经过的黑节点数一样多。
- 后两条合起来保证：最长路径（红黑相间）不超过最短路径（全黑）的 2 倍，所以树高 ≤ 2·log₂(n+1)，查找最坏也是 O(log n)。
实测 每次插入后，用反射读 TreeMap 的 root 和每个 Entry 的 left / right / color，形状写成“(根 左 右)”，R 红 B 黑：放完 7 个后是 (20B (10R (5B 1R ·) 15B) (30B 25R ·))。演示每插完一个数，下面也会打出同样格式的形状，前 7 个和实测逐一对得上。修复逻辑照 JDK 17 TreeMap.fixAfterInsertion 写，在 node 里跑过。
// Top 10：大小为 10 的小顶堆
PriorityQueue<Integer> heap = new PriorityQueue<>(11);
for (int a : amount) {
if (heap.size() < 10) heap.offer(a);
else if (a > heap.peek()) { heap.poll(); heap.offer(a); }
}
// 第一个 >= key 的下标
static int lowerBound(long[] a, long key) {
int lo = 0, hi = a.length; // [lo, hi)
while (lo < hi) {
int mid = (lo + hi) >>> 1; // 不会溢出
if (a[mid] < key) lo = mid + 1; else hi = mid;
}
return lo;
}
// 滑动窗口限流
Deque<Long> q = recent.computeIfAbsent(user, k -> new ArrayDeque<>());
while (!q.isEmpty() && q.peekFirst() <= now - 60_000) q.pollFirst();
if (q.size() >= 5) return false;
q.addLast(now); return true;
// 对账：两轮稳定排序
orders.sort(comparingLong(Order::ts));
orders.sort(comparingInt(Order::amountCents));== 1. 100 万单里找最大的 10 单 == 全部排序再取前 10 77.6 ms 大小为 10 的小顶堆 3.3 ms Stream sorted().limit(10) 468.5 ms == 2. 按时间查 [t1, t2) == 二分：比较 40 次，命中 1621 单 从头扫：比较 1000000 次，命中 1621 单 == 3. 60 秒内最多 5 单 == 0s 放行 5s 放行 10s 放行 20s 放行 30s 放行 40s 拒绝 55s 拒绝 61s 放行 66s 放行 125s 放行 == 4. 对账排序 == [0元#9527, 0元#9530, 0元#9533, 100元#9528, 100元#9531, 100元#9534, 200元#9529, 200元#9532] 比较器相等时返回 -1：第 3 次随机数据报 Comparison method violates its general contract! == 5. TreeMap 里的红黑树 == 放 10 后：10B 放 20 后：(10B · 20R) 放 30 后：(20B 10R 30R) 放 15 后：(20B (10B · 15R) 30B) 放 25 后：(20B (10B · 15R) (30B 25R ·)) 放 5 后：(20B (10B 5R 15R) (30B 25R ·)) 放 1 后：(20B (10R (5B 1R ·) 15B) (30B 25R ·))
第 5 段要加 --add-opens java.base/java.util=ALL-UNNAMED 才能反射读 TreeMap 内部。完整代码：study-labs/java/javase/algorithms-everyday →
⑥边界和变体
注意事项：不知道就会出事故
- 现象
- 线上偶发
IllegalArgumentException: Comparison method violates its general contract!，数据少时从不出现。⑤ 实测第 3 次随机数据 - 根源
- 比较器必须自反、对称、传递，相等时返回 0。写成
a > b ? 1 : -1，两个相等的数 compare(a,b) 和 compare(b,a) 都是 −1，TimSort 合并时发现前后矛盾就抛异常（JDK 7 起）。 - 做法
- 用
Comparator.comparing…、Integer.compare；多字段用thenComparing；有 null 用nullsFirst。
- 现象
(a, b) -> a.amount - b.amount，金额差超过 21 亿分（约 2147 万元）时溢出成负数，大额订单排到了前面。- 根源
- int 相减可能越界，符号反过来。
- 做法
Integer.compare(a, b)，或Comparator.comparingInt。
- 现象
- 死循环、漏掉最后一个元素、数组很大时下标变成负数抛 ArrayIndexOutOfBounds。
- 根源
- 开闭区间没想清楚，
lo = mid在只剩两个元素时不再前进；(lo + hi) / 2在 lo + hi 超过 21 亿时溢出（JDK 自己的 binarySearch 在 2006 年修过这个 bug）。 - 做法
- 固定一种写法（⑤ 的半开区间 lower bound），
mid = (lo + hi) >>> 1；能用Arrays.binarySearch、TreeMap 的ceilingKey / subMap就别手写。
- 现象
Collections.binarySearch返回一个负数，可元素明明在列表里。- 根源
- 二分的前提是有序，而且排序用的比较规则要和查找时一致。不报错，只是结果不可信。
- 做法
- 数据会变就用 TreeMap / TreeSet；一定要二分，先排序，用同一个 Comparator 查。
- 现象
- 代码看起来最优雅，100 万单却要 468.5 ms，比堆慢 140 倍。⑤ 实测
- 根源
- sorted 是有状态操作，要先收齐全部元素整体排序（见 Stream 那页④-3），再加上 100 万次装箱。
- 做法
- 数据大时用小顶堆；数据在数据库里就交给
ORDER BY … LIMIT 10加索引（J06）。
- 现象
- 递归遍历商品类目树、递归 DFS，某个数据层级特别深（或成了环）时栈溢出。
- 根源
- 每层递归占一个栈帧，线程栈默认大小有限（常见 512 KB～1 MB，取决于平台和
-Xss），几千到几万层就满了。 - 做法
- 改成显式栈或队列的迭代写法；树形数据加 visited 防环；深度不可控时别用递归。
使用规范
写之前问一句：这个集合会长到多大？循环里有没有隐藏的 O(n)（contains、indexOf、remove(0)）？
数据量一涨接口就超时。
comparing、thenComparing、reversed、nullsLast，不手写 if-else 返回 1 / −1。
坑 1、坑 2。
排序、二分、堆、平衡树、双端队列都现成，手写只在面试和 JDK 没有的结构时。
边界 bug。
Top K、范围查询、分组计数，交给 SQL 加索引，比捞到 Java 里算省得多。
把 100 万行搬进内存。
深处：面试和下一步
红黑树为什么最多转两次
插入后的修复只有三种情形：叔叔是红的，就把父亲和叔叔染黑、祖父染红，问题上移两层（只变色，不旋转，可能一路到根）；叔叔是黑的、且自己和父亲在同一侧，绕祖父转一次再变色，结束；在不同侧，先绕父亲转一次变成同侧，再按同侧处理，结束。所以旋转最多两次，变色最多 O(log n) 次。
为什么 HashMap 的树化、TreeMap、Linux 内核的调度器都选红黑树而不是 AVL 树：AVL 更严格平衡、查得略快，但插入删除要转更多次；红黑树写多读多都均衡。数据库索引则选 B+ 树：一个节点放几百个 key，树只有三四层，适合磁盘按页读（J06）。
面试题型地图（只列出路）
| 哈希 | 两数之和、字母异位词分组、最长连续序列 |
|---|---|
| 双指针 | 三数之和、盛最多水的容器、合并两个有序数组 |
| 滑动窗口 | 无重复字符的最长子串、滑动窗口最大值（单调队列） |
| 二分 | 搜索插入位置、旋转数组找最小值、在排序数组中找首尾位置 |
| 堆 | 前 K 个高频元素、合并 K 个有序链表、数据流的中位数 |
| 链表 | 反转链表、环形链表、LRU 缓存（见 HashMap 的亲戚们） |
| 树、BFS / DFS | 二叉树层序遍历、最大深度、岛屿数量、课程表（拓扑排序） |
| 递归回溯 | 全排列、子集、组合总和 |
| 动态规划 | 爬楼梯、打家劫舍、最长递增子序列、零钱兑换、编辑距离 |
每类先做第一题吃透模板，再做后面的。都是 LeetCode 上的经典题名，搜名字就能找到。
堆的另一个用法：多路归并
“合并 K 个有序链表”“把 8 张分表的订单按时间合成一个流”（J11 分库分表后的跨表查询）：把每一路的第一个元素放进小顶堆，每次弹出最小的，再把它那一路的下一个补进来。K 路总共 n 个元素，O(n log K)。数据库的外部排序、Kafka 消费多个分区按时间合并，都是这个形状。
版本差异
| JDK 7 | 对象排序换成 TimSort（违反约定开始抛异常，-Djava.util.Arrays.useLegacyMergeSort=true 可退回旧实现）；基本类型换成双轴快排 |
|---|---|
| JDK 8 | HashMap 链表过长转红黑树；Arrays.parallelSort |
| JDK 14 | 双轴快排重写，混入堆排序兜底和并行化 |
按文档和 JDK 17 源码（TimSort 的 MIN_MERGE = 32、DualPivotQuicksort）写，没有跑 7 和 14 对比。
从 100 万个数里找最大的 10 个，怎么做？复杂度？
大小为 10 的小顶堆，堆顶是门槛，比门槛大才换进来。O(n log K)（④-3）。数据放不进内存就分块各求 Top K 再合并。
Java 的 Arrays.sort 用什么算法？为什么对象和基本类型不一样？
对象用 TimSort（稳定，利用已有有序片段），基本类型用双轴快排（原地、快，稳定没意义）（④-5）。
红黑树有哪些性质？为什么能保证 O(log n)？
根黑、红节点孩子必黑、每条到空节点的路径黑节点数相同；所以最长路径不超过最短的 2 倍，树高 ≤ 2log(n+1)。插入修复最多两次旋转（⑤、⑥-3）。
怎么实现“1 分钟内最多 5 次”的限流？
单机：每个用户一个时间戳队列，滑动窗口，O(1) 均摊（④-4）。多实例：Redis 的 ZSet 存时间戳，或者令牌桶（J12）。
- 红黑树的删除（比插入更复杂，情形更多），以及 TreeMap 的
deleteEntry - B+ 树：MySQL 索引为什么是它（J06）
- 跳表：Redis ZSet 为什么不用红黑树（见 Redis 数据结构与编码那页）
- 一致性哈希：分库分表、缓存集群怎么分片（J11）
- 按上面的题型地图，每周 5 题，做完一类回来写一篇“模板”
↺回到⑤：改造你的案例
1. 热销 Top 10 带商品名
把⑤的 int 换成 record Sale(long skuId, long qty)，用 PriorityQueue<Sale>(comparingLong(Sale::qty)) 求 Top 10，最后按销量从高到低输出。
用到：④-3、坑 2
2. 用 TreeMap 换掉二分
把时间戳放进 TreeMap<Long, Order>，用 subMap(t1, true, t2, false).size() 求时间段订单数，对比和二分的结果、耗时；再往里插新订单，看谁更方便。
用到：③、⑤ 红黑树
3. 修好比较器
把⑤第 4 段的 a > b ? 1 : -1 改成 Integer::compare，跑 500 次确认不再报错。
用到：坑 1
自测
1. 用一句话说出这页的精华。
先按数据量估复杂度，再按最频繁的操作把数据提前组织好：key 用哈希，最值用堆，范围用有序数组或平衡树，窗口用双端队列；JDK 都有现成的，自己写对比较器和边界。
2. 朴素做法最疼在哪？
每次都把全部数据看一遍或排一遍，做了大量不需要的工作，也没利用数据已有的顺序（②）。
3. “Comparison method violates its general contract”的根源是哪条原理？
TimSort 依赖比较器自反、对称、传递，合并时发现矛盾就抛异常（④-5，坑 1）。
4. 预测：在⑤的红黑树里接着插入 12，会发生什么？
12 比 20 小、比 10 大、比 15 小，落在 15 的左边，是红的；父亲 15 是黑的，规则没被破坏，不用修。在演示里输入 12 点“插入”可以验证。
5. 预测：Top K 的 K 从 10 变成 50 万，小顶堆还比全排序快吗？
不一定。复杂度变成 O(n log K)，log 50 万 ≈ 19，和全排序的 log n ≈ 20 差不多，堆的常数还更大（对象装箱、比较器），这时直接排序或用快速选择（O(n) 平均）更合适（④-3）。
6. 放回全景：第 9 站前后各发生了什么？这一页讲的东西用错了，整条链路会怎样？
前面是第 8 站把订单放进 userOrders，后面是第 10 站序列化返回。第 9 站如果不用堆、改成每次把全部待取消订单排序，后台取消线程每秒排一次几十万条，CPU 被占满，第 1 站的 Tomcat 线程跟着变慢；如果 CancelTask 的 compareTo 写成相等返回 −1，PriorityQueue 不会报错，但换成 TreeSet 或排序时就可能抛异常或丢任务。第 4 站的 HashMap 是这页“按 key 查”那一格，选错成 List，查商品就从 O(1) 变成 O(n)。