本文是 Java集合框架源码精讲 的分章阅读版。
Java 集合不是一堆孤立的类,而是针对不同存取场景优化的容器家族。把它们想象成 5 种不同设计的停车场,每种解决一类问题。
入口
↓
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ ← capacity = 10
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
↑
找第 N 个车位 → 直接开过去 O(1)
中间插一辆车 → 后面所有车都要往后挪 O(n)
oldCapacity + oldCapacity >> 1),把所有车开到新场 → O(n) 但分摊到每次 add 是 O(1)new ArrayList<>(1000) 预先建大场,避免反复扩建
head → [车A|next] → [车B|next] → [车C|next] → null
←── [prev] ←── [prev]
找第 3 个 → 从 head 一个个走过去 O(n)
头部加车 → 改两个标签 O(1)
尾部加车 → 改两个标签 O(1)(有 tail 指针)
车位 = hash(key) & (capacity - 1)
车库布局(数组 + 链表 + 红黑树):
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ ← table 数组
└─┬──┴────┴─┬──┴────┴─┬──┴────┴────┴────┘
│ │ │
↓ ↓ ↓
[车A] [车B] [车D]→[车E]→[车F]→[车G]→[车H]→...≥8 → 红黑树
│ │
↓ ↓
[车C] [车I]
hash(key) 算出柜号 → 直接放进去 O(1)size > capacity * 0.75 → 容量翻倍 → 所有车重新哈希重新放为什么阈值是 8? 泊松分布概率论:哈希均匀时一个桶有 8 个元素的概率 ≈ 0.00000006,正常情况根本不会触发转树。设 8 是为了让"哈希极度不均匀(攻击)"时仍有 O(log n) 兜底。
[车M]
/ \
[车F] [车S]
/ \ / \
[车B] [车H] [车O] [车Z]
中序遍历 → B, F, H, M, O, S, Z(字典序)
subMap("a", "z"))
JDK 7:分段锁(Segment)
┌─────────┬─────────┬─────────┬─────────┐
│ Lock 1 │ Lock 2 │ Lock 3 │ Lock 4 │ 默认 16 段
│ ... │ ... │ ... │ ... │ 最大并发 = 16
└─────────┴─────────┴─────────┴─────────┘
JDK 8+:桶级锁(CAS + synchronized)
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ L │ │ L │ │ │ L │ │ │ ← 每个桶一把锁
└────┴────┴────┴────┴────┴────┴────┴────┘
最大并发 = 桶数(远大于 16)
synchronized 锁桶头节点)get 返回 null 是不存在还是值为 null"的歧义(多线程下无法用 containsKey 区分)ArrayList=连续编号 / LinkedList=链式标签 / HashMap=智能编号(哈希)/ TreeMap=排序树 / ConcurrentHashMap=多层独立锁
记住这个画面,下文所有源码、扩容、面试题都是在填充细节——骨架已经在脑子里了。