集合体系与源码

1. 这是什么

集合是 Java 最核心的基础设施之一，用来管理对象的存储、查找、去重、排序和遍历。
学习集合不能只停留在 API 层面，更要理解底层结构、时间复杂度和适用场景。

一句话理解：

集合解决的是“如何更高效地组织数据”。
源码分析解决的是“为什么这个集合在这个场景里更合适”。

2. 为什么重要

集合选型会直接影响性能、可读性和并发安全：

选错集合，业务代码可能能跑，但会越来越慢。
不理解底层结构，很容易把“偶尔慢”误判成“数据库慢”或“JVM 慢”。
很多线上问题本质上都和数据结构选择有关，比如扩容抖动、哈希冲突、并发读写、遍历成本。

换句话说，集合不是语法附属品，而是 Java 开发中的基础工程能力。

3. 先建立直觉：为什么需要这么多集合

如果只有数组，会遇到很多限制：

长度固定，不方便动态增加元素
查重不方便
按 key 查值不方便
排序和范围查询不方便
并发场景不安全

不同集合，本质上是在解决不同问题：

需求	更适合的集合方向
保持插入顺序、支持按下标访问	`List`
元素去重	`Set`
键值映射	`Map`
头尾插入删除频繁	`Deque` / `Queue`
需要排序或范围查询	`TreeMap` / `TreeSet`
多线程下共享访问	`ConcurrentHashMap` 等并发集合

所以，学习集合的关键不是背名字，而是理解“问题类型”和“结构选择”的对应关系。

4. 集合体系怎么理解

4.1 `Collection` 和 `Map` 不是一回事

Java 集合框架里：

Collection 是单值元素集合的根接口
Map 是键值对结构，不继承 Collection

可以简单记成：

Collection 管的是“一个一个的元素”
Map 管的是“key -> value 的映射关系”

4.2 常见体系速览

text

Iterable
 └─ Collection
    ├─ List
    │  ├─ ArrayList
    │  └─ LinkedList
    ├─ Set
    │  ├─ HashSet
    │  ├─ LinkedHashSet
    │  └─ TreeSet
    └─ Queue / Deque
       ├─ LinkedList
       └─ ArrayDeque

Map
 ├─ HashMap
 ├─ LinkedHashMap
 ├─ TreeMap
 └─ ConcurrentHashMap

4.3 这一章最值得先抓住的几个实现类

ArrayList：最常用的顺序表，底层是动态数组
LinkedList：双向链表，同时实现了 List 和 Deque
HashMap：最常用的键值容器，底层是数组 + 链表/红黑树
HashSet：本质上基于 HashMap 实现的去重集合
TreeMap / TreeSet：基于红黑树，适合排序和范围操作
ConcurrentHashMap：高并发场景下的线程安全 Map

5. `ArrayList` 为什么是默认首选

5.1 底层结构

ArrayList 底层是连续内存上的动态数组。

可以把它想象成：

有一个真正存数据的数组
有一个 size 记录当前用了多少个元素
当空间不够时，自动创建更大的数组并搬迁旧数据

这也是为什么它：

按下标读取快
尾部追加通常快
中间插入和删除通常慢

5.2 源码设计重点

ArrayList 源码里最重要的几个概念：

elementData：真正存元素的数组
size：当前有效元素个数
grow()：扩容逻辑

以常见 JDK 实现为例：

无参构造创建时，不会立刻分配一个很大的数组
第一次 add 时才开始分配容量
后续容量不足时，通常按约 1.5 倍扩容

为什么不是每次只加 1？

如果每次只扩 1，插入很多元素时会频繁复制数组，代价太高
适当按倍数扩容，可以把追加成本摊薄

5.3 时间复杂度怎么来的

操作	复杂度	原因
按下标读取 `get(index)`	`O(1)`	连续数组，按偏移直接定位
尾部追加 `add(e)`	平均 `O(1)`	大多数时候直接放尾部，偶尔扩容
指定位置插入 `add(index, e)`	`O(n)`	需要整体搬移后半段元素
指定位置删除 `remove(index)`	`O(n)`	删除后要整体前移
查找 `contains`	`O(n)`	需要线性扫描

5.4 什么时候该优先用它

适合：

读多写少
尾部追加多
需要按下标访问
大多数业务列表场景

不适合：

频繁在头部或中间插入删除
非常关注扩容抖动但又没预估初始容量

一个常见优化点：

如果你大概知道元素数量，尽量在创建时指定初始容量，减少扩容次数

java

List<String> list = new ArrayList<>(1024);

6. `LinkedList` 不是“插入快”这么简单

6.1 底层结构

LinkedList 底层是双向链表。
每个节点通常会保存：

当前元素
前驱节点引用
后继节点引用

6.2 它快在哪里，慢在哪里

很多人会记住一句话：“链表插入删除快”。
这句话不完整，准确说法应该是：

如果你已经拿到了目标节点位置，链表插入删除可以很快
如果你是按下标找位置，先查找节点本身就要 O(n)

所以：

addFirst、addLast、removeFirst、removeLast 很适合它
get(index)、add(index, e)、remove(index) 并不占优

6.3 为什么它不是默认首选

虽然链表理论上插入删除漂亮，但在现代 JVM 和 CPU 上，LinkedList 并不总比 ArrayList 快，原因包括：

节点对象多，额外内存开销更大
节点分散，缓存局部性差
遍历和随机访问都不如连续数组友好

工程上更实用的结论是：

绝大多数普通列表场景优先 ArrayList
真正需要双端队列语义时，多考虑 ArrayDeque
只有确实需要链表特性时再选 LinkedList

7. `HashMap` 为什么是 Java 最常用的 `Map`

7.1 底层结构

HashMap 底层不是单一结构，而是组合结构：

先用数组做主干
每个数组槽位叫 bucket（桶）
同一个桶里发生哈希冲突时，再用链表或红黑树保存多个元素

可以理解成：

先通过 hash 快速定位大致范围
再在桶内继续精确比较 key

7.2 `put` 大致做了什么

理解源码时，可以先抓住这条主流程：

计算 key 的 hash
根据数组长度计算桶下标
如果桶为空，直接放入
如果桶不为空，比较是否是同一个 key
如果冲突，沿链表或树继续查找
如果找到同 key，就覆盖旧值
如果没找到，就追加新节点
如果元素总数超过阈值，触发扩容

7.3 为什么要做 hash 扰动

源码中会对 hashCode() 的结果做一次高位参与的扰动处理，目的是：

让高位信息也参与桶分布
减少因为低位分布差导致的冲突

你不需要死记源码表达式，但要知道它是在“尽量分散冲突”。

7.4 为什么既有链表又有红黑树

这是 HashMap 的关键设计点之一。

当冲突较少时：

链表结构简单
节点少时遍历成本也可接受

当冲突很多时：

单桶里的链表会变长
查找性能会退化

因此在 Java 8 及之后的常见实现里：

当桶内节点数达到一定阈值时，会考虑树化
当容量足够大且冲突仍集中时，链表会转成红黑树

这样做的目的不是“让 HashMap 变成排序容器”，而是为了降低极端冲突下单桶查找的成本。

常见记忆点：

链表过长会考虑树化
容量太小时更倾向先扩容，而不是立刻树化

7.5 扩容为什么贵

HashMap 扩容通常会带来：

创建更大的数组
把原桶中的元素重新分布到新桶中

这不是简单复制，而是一次重新定位过程。
所以如果你能预估条目数量，合理指定初始容量，会明显减少扩容成本。

java

Map<String, Object> map = new HashMap<>(1024);

7.6 `hashCode` 和 `equals` 为什么必须一起正确实现

HashMap 判断 key 是否是“同一个逻辑对象”，依赖两步：

先看 hash 是否可能落到同一桶
再用 equals 做最终比较

如果你只重写一个，不重写另一个，就容易出现：

逻辑上相等的 key 放进了不同位置
get 不到之前 put 的值
HashSet 去重失效

这是集合使用里最常见、也最隐蔽的 bug 来源之一。

8. `Set`、有序集合和红黑树怎么理解

8.1 `HashSet` 的本质

HashSet 本质上是“只关心 key、不关心 value 的 HashMap”。

所以它的特性也来自 HashMap：

去重依赖 hashCode + equals
元素无序
查询和插入平均性能通常较好

8.2 `LinkedHashMap` / `LinkedHashSet`

如果你希望：

保留插入顺序
遍历顺序稳定

那就比 HashMap / HashSet 更适合用 LinkedHashMap / LinkedHashSet。

它们本质上是在哈希结构之外，再维护了一条顺序链。

8.3 `TreeMap` / `TreeSet`

如果你需要：

元素天然有序
按范围查询
取最小值、最大值、前驱、后继

那就应该考虑 TreeMap / TreeSet。

它们底层基于红黑树，典型特点是：

不追求哈希意义下的平均 O(1)
更强调有序性和稳定的对数级操作成本

这类集合不是 HashMap 的替代品，而是解决另一类问题。

9. `ConcurrentHashMap` 和 `HashMap` 的核心差异

9.1 为什么不能在并发写场景直接用 `HashMap`

HashMap 不是线程安全的。
多个线程同时读写时，可能出现：

数据覆盖
读到不一致结果
扩容期间行为不可控

所以：

单线程或只读场景可以用 HashMap
多线程共享更新场景优先考虑 ConcurrentHashMap

9.2 `ConcurrentHashMap` 的设计思路

在 Java 8 之后的常见实现中，它不再是早期版本那种“分段锁”主导的设计。
更高层地理解，它结合了这些手段：

volatile 保证可见性
CAS 处理无锁更新机会
在必要位置用更细粒度同步保护桶

你不需要一开始就死抠每一行源码，但要知道它的目标是：

尽量减少全表级别锁竞争
让读操作和大部分并发访问更高效

9.3 一个很容易忽略的区别

ConcurrentHashMap 不允许：

null key
null value

因为在并发语义下，null 容易让“值不存在”和“值正在变化”之间的语义变得模糊。

10. 选型时怎么快速判断

10.1 常见集合选型表

场景	更推荐的集合	原因
普通列表、按下标访问、尾部追加	`ArrayList`	默认最实用，随机访问快
双端队列、栈、队列	`ArrayDeque`	通常比 `LinkedList` 更轻量
既要 `List` 语义又要频繁头尾操作	`LinkedList`	双向链表，头尾操作方便
无序去重	`HashSet`	基于哈希，平均性能好
保持插入顺序去重	`LinkedHashSet`	去重同时保序
无序键值映射	`HashMap`	最常用的键值结构
保持插入顺序的键值映射	`LinkedHashMap`	遍历顺序稳定
排序、范围查询	`TreeMap` / `TreeSet`	红黑树支持有序操作
并发共享键值映射	`ConcurrentHashMap`	线程安全且性能更合理

10.2 不要只背“底层结构”，更要背“决策方式”

真正实用的判断顺序通常是：

先问是否需要 key-value
再问是否需要去重
再问是否需要顺序或排序
再问是否需要频繁随机访问
最后再问是否有并发要求

这样你会比单纯背“数组、链表、红黑树”更容易做对选型。

11. 常见问题

11.1 把所有列表都写成 `LinkedList`

这是非常常见的误区。
很多人以为链表“插入删除快”，就默认比 ArrayList 高级。实际上多数业务代码里：

随机访问多
中间节点定位少不了
CPU 缓存和对象分配成本也不能忽略

结果往往是 ArrayList 更合适。

11.2 只会用 `HashMap`，不会分析 key 设计

如果 key 的 hashCode 分布很差，或者 equals / hashCode 实现不一致：

冲突会增加
查询效率会下降
甚至语义会出错

问题不一定出在 HashMap，可能出在 key 设计。

11.3 对扩容毫无概念

如果一个大集合不断增长，但你又不给初始容量：

ArrayList 会多次扩容复制
HashMap 会多次扩容重分布

程序不是不能跑，但高峰期很容易抖。

11.4 在并发更新场景继续使用 `HashMap`

只要有多线程共享写入，就不能再把它当成“只是个普通容器”。
线程安全不是靠运气，而是靠结构设计保障。

12. 动手验证

这一节可以直接复制运行，边看边验证。

12.1 准备一个可运行示例

新建文件 CollectionSourceDemo.java，内容如下：

java

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.RandomAccess;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class CollectionSourceDemo {
    static final class BadKey {
        private final int id;

        BadKey(int id) {
            this.id = id;
        }

        @Override
        public int hashCode() {
            return 1;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (!(obj instanceof BadKey)) {
                return false;
            }
            BadKey other = (BadKey) obj;
            return id == other.id;
        }

        @Override
        public String toString() {
            return "K" + id;
        }
    }

    private static int arrayListCapacity(ArrayList<?> list) throws Exception {
        Field field = ArrayList.class.getDeclaredField("elementData");
        field.setAccessible(true);
        Object[] data = (Object[]) field.get(list);
        return data.length;
    }

    private static String firstBucketNodeClass(HashMap<?, ?> map) throws Exception {
        Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] table = (Object[]) tableField.get(map);
        for (Object node : table) {
            if (node != null) {
                return node.getClass().getName();
            }
        }
        return "empty";
    }

    public static void main(String[] args) throws Exception {
        ArrayList<Integer> arrayList = new ArrayList<>();
        System.out.println("arrayListCapacityBeforeAdd=" + arrayListCapacity(arrayList));
        for (int i = 0; i < 11; i++) {
            arrayList.add(i);
        }
        System.out.println("arrayListSize=" + arrayList.size());
        System.out.println("arrayListCapacityAfter11Add=" + arrayListCapacity(arrayList));
        System.out.println("arrayListRandomAccess=" + (arrayList instanceof RandomAccess));

        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.addFirst(10);
        linkedList.addLast(20);
        linkedList.addLast(30);
        System.out.println("linkedListAsDeque=" + linkedList);
        System.out.println("linkedListRemoveFirst=" + linkedList.removeFirst());
        System.out.println("linkedListAfterRemove=" + linkedList);
        System.out.println("linkedListRandomAccess=" + (linkedList instanceof RandomAccess));

        HashSet<String> set = new HashSet<>();
        set.add("java");
        set.add("java");
        set.add("collection");
        System.out.println("hashSetSize=" + set.size());

        HashMap<BadKey, Integer> map = new HashMap<>(64);
        for (int i = 0; i < 10; i++) {
            map.put(new BadKey(i), i);
        }
        System.out.println("hashMapSize=" + map.size());
        System.out.println("hashMapGetK8=" + map.get(new BadKey(8)));
        System.out.println("hashMapFirstBucketNodeClass=" + firstBucketNodeClass(map));

        ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();
        ExecutorService pool = Executors.newFixedThreadPool(4);
        for (int t = 0; t < 4; t++) {
            pool.submit(() -> {
                for (int i = 0; i < 1000; i++) {
                    concurrentMap.merge("count", 1, Integer::sum);
                }
            });
        }
        pool.shutdown();
        pool.awaitTermination(5, TimeUnit.SECONDS);
        System.out.println("concurrentCount=" + concurrentMap.get("count"));

        try {
            concurrentMap.put("x", null);
        } catch (NullPointerException e) {
            System.out.println("concurrentHashMapNullValue=NullPointerException");
        }
    }
}

12.2 编译并运行

先编译：

bash

javac CollectionSourceDemo.java

再运行：

bash

java --add-opens java.base/java.util=ALL-UNNAMED CollectionSourceDemo

为什么这里多了 --add-opens：

示例里用了反射读取 ArrayList 和 HashMap 的私有字段
在较新的 JDK 中，不加这个参数可能会被模块系统阻止

如果你在 PowerShell 中操作，也直接执行同样两条命令即可。

12.3 你应该观察到什么

输出不一定逐字完全一致，但应包含这些关键信息：

text

arrayListCapacityBeforeAdd=0
arrayListSize=11
arrayListCapacityAfter11Add=15
arrayListRandomAccess=true
linkedListAsDeque=[10, 20, 30]
linkedListRemoveFirst=10
linkedListAfterRemove=[20, 30]
linkedListRandomAccess=false
hashSetSize=2
hashMapSize=10
hashMapGetK8=8
hashMapFirstBucketNodeClass=java.util.HashMap$TreeNode
concurrentCount=4000
concurrentHashMapNullValue=NullPointerException

12.4 每一行在验证什么

arrayListCapacityBeforeAdd=0：说明无参构造的 ArrayList 起初并不会立刻分配一个大数组
arrayListCapacityAfter11Add=15：说明它确实会在容量不足时扩容，且常见实现里扩容接近 1.5 倍
arrayListRandomAccess=true：说明它支持高效随机访问语义
linkedListAsDeque、linkedListRemoveFirst：说明 LinkedList 很适合做双端操作
linkedListRandomAccess=false：说明它不属于随机访问友好结构
hashSetSize=2：说明 Set 的核心语义是去重
hashMapGetK8=8：说明即使发生冲突，HashMap 仍能正确依赖 equals 找回值
hashMapFirstBucketNodeClass=java.util.HashMap$TreeNode：说明高冲突桶在满足条件时会树化
concurrentCount=4000：说明 ConcurrentHashMap 能支撑多线程并发更新
concurrentHashMapNullValue=NullPointerException：说明它不允许 null 值

12.5 再做两个延伸验证

你可以继续做下面两个实验：

把 HashMap<BadKey, Integer> map = new HashMap<>(64); 改成 new HashMap<>(16);
把 ArrayList<Integer> arrayList = new ArrayList<>(); 改成 new ArrayList<>(20);

你可以观察：

HashMap 树化和容量条件之间的关系
ArrayList 预设容量后，早期扩容行为是否减少

13. 练习建议

下面这些练习做完，这一章就不只是“看懂”，而是真的掌握了：

画出 Collection / Map 的常见实现类关系图
阅读 ArrayList 的 add、grow 核心逻辑，自己总结扩容流程
阅读 HashMap 的 putVal、resize 核心流程，画出插入路径
写一个类，故意把 hashCode 实现得很差，再观察冲突现象
对比 ArrayList、LinkedList、ArrayDeque 在头尾操作和随机访问上的差异
总结一份“业务场景 -> 推荐集合”的选型表

14. 自测问题

为什么大多数普通列表场景下优先选 ArrayList？
LinkedList 为什么不能简单理解成“插入删除一定更快”？
HashMap 为什么既需要数组，也需要链表或红黑树？
HashSet 去重的底层依赖是什么？
为什么 hashCode 和 equals 要一起正确实现？
ConcurrentHashMap 和 HashMap 的核心差异是什么？
TreeMap / TreeSet 适合解决哪类问题？

15. 自测核对要点

如果你的回答能覆盖下面这些点，说明这一章基本掌握到位了：

ArrayList 是动态数组，默认适合大多数列表场景
LinkedList 是双向链表，真正优势在头尾操作和队列语义，不在随机访问
HashMap 是数组 + 链表/红黑树的组合结构，目标是兼顾平均查询效率和冲突处理
HashSet 本质上依赖 HashMap
TreeMap / TreeSet 的价值在有序和范围能力
ConcurrentHashMap 解决的是并发共享访问问题，不只是“另一个 Map”
集合选型本质上是在权衡访问方式、顺序要求、去重需求、排序需求和并发要求

集合体系与源码 ​

1. 这是什么 ​

2. 为什么重要 ​

3. 先建立直觉：为什么需要这么多集合 ​

4. 集合体系怎么理解 ​

4.1 Collection 和 Map 不是一回事 ​

4.2 常见体系速览 ​

4.3 这一章最值得先抓住的几个实现类 ​

5. ArrayList 为什么是默认首选 ​

5.1 底层结构 ​

5.2 源码设计重点 ​

5.3 时间复杂度怎么来的 ​

5.4 什么时候该优先用它 ​

6. LinkedList 不是“插入快”这么简单 ​

6.1 底层结构 ​

6.2 它快在哪里，慢在哪里 ​

6.3 为什么它不是默认首选 ​

7. HashMap 为什么是 Java 最常用的 Map ​

7.1 底层结构 ​

7.2 put 大致做了什么 ​

7.3 为什么要做 hash 扰动 ​

7.4 为什么既有链表又有红黑树 ​

7.5 扩容为什么贵 ​

7.6 hashCode 和 equals 为什么必须一起正确实现 ​

8. Set、有序集合和红黑树怎么理解 ​

8.1 HashSet 的本质 ​

8.2 LinkedHashMap / LinkedHashSet ​

8.3 TreeMap / TreeSet ​

9. ConcurrentHashMap 和 HashMap 的核心差异 ​

9.1 为什么不能在并发写场景直接用 HashMap ​

9.2 ConcurrentHashMap 的设计思路 ​

9.3 一个很容易忽略的区别 ​

10. 选型时怎么快速判断 ​

10.1 常见集合选型表 ​

10.2 不要只背“底层结构”，更要背“决策方式” ​

11. 常见问题 ​

11.1 把所有列表都写成 LinkedList ​

11.2 只会用 HashMap，不会分析 key 设计 ​

11.3 对扩容毫无概念 ​

11.4 在并发更新场景继续使用 HashMap ​

12. 动手验证 ​

12.1 准备一个可运行示例 ​

12.2 编译并运行 ​

12.3 你应该观察到什么 ​

12.4 每一行在验证什么 ​

12.5 再做两个延伸验证 ​

13. 练习建议 ​

14. 自测问题 ​

15. 自测核对要点 ​

集合体系与源码

1. 这是什么

2. 为什么重要

3. 先建立直觉：为什么需要这么多集合

4. 集合体系怎么理解

4.1 `Collection` 和 `Map` 不是一回事

4.2 常见体系速览

4.3 这一章最值得先抓住的几个实现类

5. `ArrayList` 为什么是默认首选

5.1 底层结构

5.2 源码设计重点

5.3 时间复杂度怎么来的

5.4 什么时候该优先用它

6. `LinkedList` 不是“插入快”这么简单

6.1 底层结构

6.2 它快在哪里，慢在哪里

6.3 为什么它不是默认首选

7. `HashMap` 为什么是 Java 最常用的 `Map`

7.1 底层结构

7.2 `put` 大致做了什么

7.3 为什么要做 hash 扰动

7.4 为什么既有链表又有红黑树

7.5 扩容为什么贵

7.6 `hashCode` 和 `equals` 为什么必须一起正确实现

8. `Set`、有序集合和红黑树怎么理解

8.1 `HashSet` 的本质

8.2 `LinkedHashMap` / `LinkedHashSet`

8.3 `TreeMap` / `TreeSet`

9. `ConcurrentHashMap` 和 `HashMap` 的核心差异

9.1 为什么不能在并发写场景直接用 `HashMap`

9.2 `ConcurrentHashMap` 的设计思路

9.3 一个很容易忽略的区别

10. 选型时怎么快速判断

10.1 常见集合选型表

10.2 不要只背“底层结构”，更要背“决策方式”

11. 常见问题

11.1 把所有列表都写成 `LinkedList`

11.2 只会用 `HashMap`，不会分析 key 设计

11.3 对扩容毫无概念

11.4 在并发更新场景继续使用 `HashMap`

12. 动手验证

12.1 准备一个可运行示例

12.2 编译并运行

12.3 你应该观察到什么

12.4 每一行在验证什么

12.5 再做两个延伸验证

13. 练习建议

14. 自测问题

15. 自测核对要点