主题
界面
树、堆与哈希表
1. 本节定位
《数据结构：数组、链表、栈与队列》的数组与链表是线性结构；本节进入非线性结构：
text
线性结构：一个接一个（数组、链表、栈、队列）
树： 一对多 → 有序、范围查询 ✓
堆： 只关心"最值" → Top K、优先队列 ✓
哈希表： 靠计算定位 → O(1) 精确查找 ✓✓三者的分工是本节的主线 ✓ ——选错结构，性能差几个数量级 ✓
2. 学习目标
- 说出树/堆/哈希表各自擅长什么查询 ★★★；
- 能解释哈希表"平均 O(1)、最坏 O(n)" ★★★（含实测）；
- 知道自定义类做 key 必须重写
hashCode与equals★★★； - 知道"Top K 用堆而不是排序" ★★★（含实测）；
- 知道递归遍历的栈深度风险 ★★（含实测）。
3. 前置知识检查
- 知道
HashMap的基本用法吗？（《迭代器与集合遍历陷阱》）✓ - 知道
PriorityQueue吗？（《泛型基础》）✓
4. 为什么需要这个知识
先看一个真实事故 ✗：
java
class User {
private String id;
// 只重写了 equals，忘了 hashCode ← 事故源头
}
Map<User, Order> map = new HashMap<>();
map.put(new User("U1"), order);
map.get(new User("U1")); // ✗ 返回 null —— 数据"消失"了★ 实测数据告诉你不重写 hashCode 的代价 ✓：
text
正常 hashCode：插入 20000 次 + 查询 20000 次 → 27 ms
全部同 hashCode：仅插入 20000 次 → 2062 ms ✗✗
全部同 hashCode：查询 20000 次 → 2042 ms ✗✗76 倍的差距 ✗✗ ——而且这个 bug 不会报错，只是"越来越慢" ✓✓
5. 核心概念
5.1 三种结构的分工 ★★★
| 结构 | 擅长 | 复杂度 | 不擅长 |
|---|---|---|---|
| 哈希表 ★★★ | 按 key 精确查找 ✓ | 平均 O(1) ✓✓ | 范围查询、有序遍历 ✗ |
| 平衡树（红黑树/B+树） ★★ | 有序、范围、第 k 小 ✓ | O(log n) ✓ | 实现复杂 ⚠️ |
| 堆 ★★ | 取最值、Top K ✓ | 取最值 O(1)，插入删除 O(log n) ✓ | 查任意元素 ✗ |
★ 一句话判断：
text
"我要查 U1 的订单" → 哈希表 ✓
"我要查 2026 年 1~3 月的订单" → 有序结构（B+树索引）✓
"我要销售额前 10 的商品" → 堆 ✓★ 一个常见误区 ✗：
"哈希表最快，那全用哈希表" ✗✗
范围查询在哈希表上只能全表扫描 ✗ ——这就是为什么数据库索引用 B+ 树而不是哈希 ✓✓ （哈希索引只支持等值查询，MySQL 的 Memory 引擎就是这样）✓
5.2 哈希表：平均 O(1) 与最坏 O(n) ★★★
哈希表的三个要素：
text
① 哈希函数：key → 桶下标 hash(key) & (capacity - 1)
② 冲突处理：不同 key 落到同一桶 → 链表 / 红黑树
③ 扩容：元素变多时重建 → 负载因子 0.75实测数据：
text
正常 hashCode（分布均匀）： 27 ms ✓
全部同 hashCode（全落一桶）：2062 ms ✗✗ ← 76 倍★ 为什么是 76 倍 ✓：
所有 key 落进同一个桶 → HashMap 退化成一条链表 ✓
查找从 O(1) 变成 O(n) ✗ ——2 万次查询就是 2 万 × 2 万 / 2 = 2 亿次比较 ✓✓
★ JDK 8 的补救 ✓：
text
桶内链表长度 > 8 → 转成红黑树于是最坏情况从 O(n) 降到 O(log n) ✓✓ ——但"红黑树"只在冲突极端严重时才启用 ✓
★ 所以自定义 key 的规矩 ✓✓：
| 规矩 | 说明 |
|---|---|
重写 hashCode ★★★ | 且要"分布均匀" ——别写 return 1; ✗✗ |
重写 equals ★★★ | HashMap 判定"同一个 key"用的是 equals ✓ |
| 两者要一致 ★★ | equals 相等的两个对象，hashCode 必须相等 ✓（反之不要求 ✓） |
| 用于计算的字段不可变 ★★ | 否则放进 Map 后再改，就再也找不到了 ✗✗ |
★ 最后一条特别隐蔽 ✗：
java
Map<List<String>, Integer> map = new HashMap<>();
List<String> key = new ArrayList<>(List.of("a"));
map.put(key, 1);
key.add("b"); // ✗ 改了 key！
map.get(key); // null —— 用它的"新哈希"找不到旧位置 ✓★ 最省事的写法（推荐）✓：
java
// 用 record（Java 16+）：自动生成正确的 hashCode 与 equals
public record UserKey(String tenantId, String userId) { }
// 或者用 IDE 生成，或者 Objects.hash(...)
@Override public int hashCode() { return Objects.hash(tenantId, userId); }
@Override public boolean equals(Object o) { ... }5.3 扩容：负载因子与预设容量 ★★
实测数据：
text
默认容量（反复扩容）：327 ms
预设容量： 364 ms
→ 差异 11%（本次测量未显示优势：一次性分配 700 万桶的大数组本身也有成本）★ 这个"反直觉结果"要说清楚 ✓★：
| 观察 | 解释 |
|---|---|
| 预设容量没有更快 ✗ | 一次性分配 700 万个桶的数组，本身就要与 GC 打交道 ✓ |
| 但预设容量仍有意义 ✓ | 它消除的是"增量扩容带来的抖动" ✓✓ |
★ 结论要精确表述 ✓✓：
预设容量不是"为了更快"，而是"为了消除偶发的长停顿" ✓✓
对延迟敏感的服务（P99 有要求），一次扩容引起的停顿就可能触发超时 ✗
对吞吐型批处理，预设容量的收益不明显 ✓
★ 负载因子 0.75 的取舍 ✓：
| 因子 | 效果 |
|---|---|
| 太大（如 0.95） ✗ | 冲突变多，查询变慢 |
| 太小（如 0.5） ✗ | 内存浪费一半 |
| 0.75 ★★ | 时间与空间的折中（官方给出的经验值）✓ |
★ 计算预设容量的公式（可以直接用）✓：
java
int expected = 1000;
Map<String, Object> map = new HashMap<>((int) (expected / 0.75f) + 1); // 13345.4 树：什么时候需要它 ★★
树的价值在"有序" ✓ ——这是哈希表给不了的 ✓：
| 树的用法 | 复杂度 | 用途 |
|---|---|---|
范围查询（BETWEEN）★★ | O(log n + k) | 数据库索引（B+ 树） ✓ |
| 第 k 小 / 排名 ★ | O(log n) | 排行榜 ✓ |
| 有序遍历 ★ | O(n) | 输出有序结果 ✓ |
| 前缀查找 ★ | O(log n) | Trie（前缀树） ✓ |
★ 二叉树的一个重要性质 ✓：
平衡二叉树的深度是 O(log n) ——10 亿节点也只有 30 层 ✓✓
所以平衡树上的递归遍历是安全的 ✓（深度只有 30 ✓）
但"退化"的树不是 ✗ ——实测：
text
树深度：10000（退化成链表的最坏情况）
递归遍历：成功 ← 1 万层恰好没溢出
迭代遍历：成功，节点数 10000 ✓★ 关于"递归会不会栈溢出" ✓：
| 深度 | 结果 |
|---|---|
| 几百 ✓ | 完全安全 |
| 1 万 ⚠️ | 临界（本次成功，但换个 JVM 参数/线程栈大小就可能失败） |
| 10 万 ✗✗ | 必然 StackOverflowError |
★ 所以工程上两条规矩 ✓✓：
- 平衡树用递归没问题（深度 O(log n)）✓；
- "深度可能不确定"的遍历（链表状结构、文件目录、用户输入）用迭代 + 显式栈 ✓✓
★ 顺带说明"显式栈"的代价：它把内存从"JVM 栈"挪到了"堆" ✓ ——堆更大，但也要注意 OOM ⚠️
5.5 堆：Top K 为什么不用排序 ★★★
实测数据：
text
n=5000000，k=10 全排序：608 ms | 小顶堆：31 ms | 结果一致：true ← 19.6 倍
n=5000000，k=1000 全排序：592 ms | 小顶堆：44 ms | 结果一致：true★ 两种做法的复杂度 ✓：
| 做法 | 复杂度 | 说明 |
|---|---|---|
| 全排序 ✗ | O(n log n) | 必须处理所有元素 |
| 小顶堆（保留 k 个） ✓✓ | O(n log k) | k 越小优势越大 ★ |
★ 用法上的关键点（很容易记反） ✓✓：
text
求"最大的 k 个" → 用"小顶堆"（堆顶是这 k 个里最小的，便于淘汰）
求"最小的 k 个" → 用"大顶堆"★ 记忆口诀 ✓："要大的，就用小的堆" ✓✓（因为堆顶要被淘汰，所以它得是"里面最差的" ✓）
★ 判断该用哪个 ✓：
| 情况 | 选择 |
|---|---|
| k 远小于 n（如 n=500 万，k=10）★★ | 堆 ✓✓ |
| k 接近 n（如 k=n/2） | 直接排序 ✓ |
| 需要"完整有序"的结果 | 必须排序 ✗（堆只能给前 k） |
★ 一个延伸：PriorityQueue 就是堆 ✓ ——它的 offer/poll 是 O(log n)，但 peek 是 O(1) ✓
★ 它的典型用途：任务调度（按优先级取任务）、合并 K 个有序链表、Dijkstra 算法 ✓
6. 递进示例
6.1 最小示例：正确的 key
java
public record OrderKey(String tenantId, String orderNo) { } // record 自动生成正确的 equals/hashCode ✓
Map<OrderKey, Order> cache = new HashMap<>();6.2 业务示例：Top K
java
// 求销售额前 10
PriorityQueue<Product> minHeap = new PriorityQueue<>(Comparator.comparingLong(Product::sales));
for (Product p : products) {
if (minHeap.size() < 10) { minHeap.offer(p); }
else if (p.sales() > minHeap.peek().sales()) {
minHeap.poll();
minHeap.offer(p);
}
}6.3 反例：用哈希表做范围查询
java
// ✗ 要找 [start, end] 范围内的数据，哈希表只能全扫
for (Map.Entry<Long, Data> e : map.entrySet()) {
if (e.getKey() >= start && e.getKey() <= end) { ... }
}
// ✓ 用 TreeMap（红黑树）
map.subMap(start, true, end, true);7. 完整可运行代码与实测
代码：labs/cs-basics/src/main/java/cn/kb/learn/cs/HashAndHeapLesson.java
运行：
powershell
cd labs
.\mvnw.cmd -pl cs-basics compile
java "-Dstdout.encoding=UTF-8" -cp cs-basics/target/classes cn.kb.learn.cs.HashAndHeapLesson实测输出（节选）：
text
===== 1. 哈希冲突的实测 =====
正常 hashCode：插入 20000 次 + 查询 20000 次 → 27 ms ✓
全部同 hashCode：仅插入 20000 次 → 2062 ms ✗✗
全部同 hashCode：查询 20000 次 → 2042 ms ✗✗
===== 4. Top K 问题 =====
n=5000000，k=10 全排序：608 ms | 小顶堆：31 ms | 结果一致：true
n=5000000，k=1000 全排序：592 ms | 小顶堆：44 ms | 结果一致：true★ 两条可直接落地的规矩 ✓：
| # | 规矩 | 依据 |
|---|---|---|
| ① | 自定义类做 Map key，必须用 record 或正确重写 hashCode + equals | 76 倍差距 ✗ |
| ② | Top K 用 PriorityQueue，不要先排序 | 19.6 倍差距 ✓ |
★ 一个测量上的教训（本类初版踩到）✓： Top K 的两种实现最初"结果不一致" ✗ ——原因是堆的 poll 顺序与排序结果的方向相反 ✓ 这类 bug 只会在"加了结果比对"之后暴露 ✓✓ ——所以"两种实现互相对照"是很有价值的测试手法 ✓
8. Debug 观察点
- 把
BadKey.hashCode()改成value % 100：观察耗时立刻下降 ★★； - 把
GoodKey改成只重写equals：观察get返回 null ✗✗； - 给
HashMap传一个巨大的预设容量（如new HashMap<>(100_000_000)）：观察 OOM 或耗时增加 ⚠️； - 把树深度从 1 万调到 10 万：观察
StackOverflowError★★； - 对同一个 Top K 问题，把 k 改成 200 万：观察堆的优势消失 ✓（k 接近 n 时排序更优 ✓）。
9. 常见错误
| # | 错误 | 说明 |
|---|---|---|
| 1 | 重写 equals 忘了 hashCode ✗✗ | 数据"查不到"（第 4 节）✗✗ |
| 2 | hashCode 返回值恒定或分布极差 ✗✗ | 退化成长链表，76 倍慢 ✓ |
| 3 | 把可变对象当 key，之后又改动它 ✗✗ | 再也找不到（5.2）✗✗ |
| 4 | 用 HashMap 做范围查询 ✗✗ | 只能全扫，要用 TreeMap ✓ |
| 5 | Top K 先全排序 ✗ | 慢 19.6 倍 ✓ |
| 6 | "求最大 k 个"用大顶堆 ✗ | 记反了 ——要用小顶堆 ✓ |
| 7 | 对"深度不确定"的结构用递归 ✗ | 栈溢出风险（5.4）✓ |
10. 动手实验
目标：亲手复现"哈希退化"与"堆的优势"。
步骤：
- 跑
HashAndHeapLesson，记录 27 ms 与 2062 ms 的对比 ✓； - 自己写一个 key 类：
hashCode返回value % 3（只有 3 个桶），测 10 万次查询耗时 ★★； - 改成正确的
hashCode，对比 ✓； - 用
PriorityQueue与Arrays.sort各求一次 Top 100（n=500 万），对比耗时 ✓； - 把树深度设为 10 万，观察栈溢出，再改成显式栈解决 ★。
验收方式：能说出"哈希表在什么条件下退化成 O(n)"。
扩展任务：实现一个支持范围查询的"分数排行榜"：
- 用
TreeMap<Long, Set<String>>（分数 → 用户集合）✓； - 实现
topN(int n)与range(long min, long max)✓； - 说明：为什么这比
HashMap更合适（提示：需要有序遍历与范围查询）✓
11. 练习题
- 判断：
HashMap的查找永远是 O(1)。（对 / 错） - 填空：哈希表退化成链表时，查找从 O(1) 变成 ______；JDK 8 用 ______ 把最坏情况降到 O(log n)。
- 简答：为什么"求最大的 k 个元素"要用小顶堆？
- （代码阅读）
java
class Key {
int id;
@Override public int hashCode() { return 1; }
@Override public boolean equals(Object o) { return o instanceof Key k && k.id == id; }
}
Map<Key, String> map = new HashMap<>();
for (int i = 0; i < 100000; i++) { map.put(new Key(i), "v" + i); }这 10 万次 put 大约要多久？为什么？ 5. （编程）用 PriorityQueue 实现"数据流的中位数"（提示：一个大顶堆 + 一个小顶堆）★★
参考答案（要点）
- 错。平均 O(1)，最坏 O(n) ✓（当所有 key 冲突时）✓★
- O(n)；红黑树（桶内链表长度 > 8 时转换）✓
- 因为小顶堆的堆顶是"这 k 个里最小的"，便于与新元素比较后淘汰 ✓★
- 会很慢（几秒级）✗ ——因为所有 key 落进同一个桶，退化成链表 ✓ —— 10 万次 put 约需 O(n²/2) 次比较 ✓
- 要点：大顶堆放较小的一半，小顶堆放较大的一半，保持两个堆大小差 ≤ 1 ✓ 中位数就是两个堆顶的平均（或其中一个） ✓
12. 掌握标准
- [ ] 能说出哈希表/树/堆各自擅长的查询类型 ★★★；
- [ ] 能解释哈希表"平均 O(1) / 最坏 O(n)"，并用实测数字说明 ★★★；
- [ ] 知道自定义 key 必须用
record或正确重写hashCode+equals★★★； - [ ] 知道可变对象不能当 key（改了之后找不到） ★★；
- [ ] 知道 Top K 用堆，且"求最大用小顶堆" ★★★；
- [ ] 知道范围查询要用
TreeMap而不是HashMap★★； - [ ] 知道"深度不确定的遍历要用显式栈" ★★。
13. 扩展资源
14. 下一步学习
《基础算法：排序与二分查找》：在有序数据上做文章。
后续知识
暂无
进度只保存在本机浏览器，可随时清除