Java 集合框架是日常开发里天天打交道、却很少有人系统梳理过的一套东西。ArrayList、HashMap 谁都会 new，但底层为什么这么设计、什么时候该用哪个、扩容和线程安全这些细节，平时零散知道一点，从没串成体系。这篇把集合框架从整体结构到 HashMap 核心实现梳理一遍，把散落的知识点归拢成一张图。

---

一、先看整体：Collection 和 Map 两大体系

Java 集合框架分两条主线：

体系	特点	常用实现
Collection	存单个元素	List / Set / Queue
Map	存键值对（key-value）	HashMap / TreeMap / LinkedHashMap

Collection 下又分三类：

• List：有序、可重复。ArrayList（动态数组）、LinkedList（链表）。
• Set：无序、不可重复。HashSet（哈希）、TreeSet（红黑树有序）。
• Queue：队列。LinkedList（双端队列）、PriorityQueue（优先队列）。

记住这张图，后面每个实现都是在"这个位置上"解决特定问题。

二、List：ArrayList vs LinkedList

两者都实现了 List，但底层结构完全不同，决定了它们各自的快慢。

	ArrayList	LinkedList
底层	动态数组	双向链表
随机访问 get(i)	O(1)	O(n)（要遍历）
增删（中间位置）	O(n)（要搬元素）	O(1)（改指针）
内存	连续、紧凑	每个节点多存前后指针

选型原则：读多写少用 ArrayList，频繁在头部/中间增删用 LinkedList。绝大多数业务场景 ArrayList 就够，LinkedList 只在"频繁头插/头删"（比如做队列、栈）时有优势。

ArrayList 扩容细节：默认初始容量 10，满了之后扩容到原来的 1.5 倍（底层 Arrays.copyOf 复制到新数组）——这也是为什么说 ArrayList 增删慢，扩容要整块搬。

三、HashMap 核心原理（重点）

HashMap 是集合框架里最值得搞懂的一个，底层从 JDK 1.7 到 1.8 有重大变化。

3.1 底层结构：数组 + 链表 + 红黑树

HashMap 本质是一张哈希表：

• 一个数组（叫桶 bucket），每个位置放一条链表（1.8 后链表过长会转红黑树）。
• 存数据时，先对 key 做哈希（hashCode() 扰动），算出它该落在数组的哪个位置，再挂到那个位置的链表/树上。

数组（桶）
[0] -> node -> node -> node          （链表）
[1] -> node
[2] -> node -> node
...

3.2 put 的完整流程

1. 对 key 算 hash；
2. 定位到数组下标 (n-1) & hash；
3. 该位置为空 → 直接放；
4. 该位置有值 → 遍历链表/树，key 相同就覆盖 value，否则追加到末尾；
5. 链表长度超过阈值（8）且数组长度 ≥ 64 → 链表转红黑树。

3.3 扩容：负载因子 0.75

• 默认初始容量 16，负载因子 0.75——即元素个数超过 16 × 0.75 = 12 就触发扩容。
• 扩容是 2 倍（16 → 32 → 64...），因为数组长度保持 2 的幂，哈希定位用 (n-1) & hash 比取模快。
• 扩容会重新哈希所有元素（rehash），代价不小，所以负载因子是在"空间利用率"和"扩容频率"之间取平衡。

3.4 JDK 1.7 vs 1.8 的变化

	JDK 1.7	JDK 1.8
结构	数组 + 链表	数组 + 链表 + 红黑树
链表插入	头插法	尾插法
哈希函数	多次扰动	简化扰动

关键两点：

1. 1.7 头插法有 bug：多线程扩容时头插法会让链表成环，导致 get 死循环（CPU 100%）。1.8 改成尾插法解决了这个问题——但注意，HashMap 本身依然不是线程安全的，只是修了死循环这个表现。
2. 为什么加红黑树：链表太长时查询退化成 O(n)，恶意构造 hash 冲突的 key 可以拖垮性能。1.8 让"链表长度 > 8 且数组长度 ≥ 64"时转成红黑树，查询回到 O(log n)。

3.5 一句话记住 HashMap

数组解决"定位快"，链表/红黑树解决"哈希冲突"，扩容（0.75、2 倍）解决"空间换时间"。

四、Set：HashSet 和 TreeSet

• HashSet：底层就是一个 HashMap，把元素当 key，value 用一个固定占位对象。所以 HashSet 的"不重复、无序、O(1) 增删查"本质就是 HashMap 的 key 特性。
• TreeSet：底层是红黑树（TreeMap），元素有序（自然顺序或比较器），增删查 O(log n)。

记住：要唯一性就用 HashSet，要"唯一 + 有序"就用 TreeSet。

五、Queue：队列

• LinkedList 实现了 Deque（双端队列），常被拿来当普通队列用（offer 入队、poll 出队）。
• PriorityQueue：优先队列，底层是二叉堆，每次出队的是优先级最高（最小/最大）的元素，不是先进先出。

六、线程安全集合（简提）

多线程环境别用上面的普通集合，用这几个：

• ConcurrentHashMap：线程安全的 Map，1.8 用 CAS + 锁单个桶 实现，读几乎无锁，性能远好于老 Hashtable。
• CopyOnWriteArrayList：写时复制，适合"读多写极少"的场景（如配置列表）。
• 老的 Vector、Hashtable：全程 synchronized，性能差，已淘汰，别用了。

七、选型对照表

需求	选什么
有序、可重复、读多	ArrayList
频繁头插/头删、做队列栈	LinkedList
键值对、无序、快	HashMap
键值对、有序	TreeMap / LinkedHashMap
唯一、无序	HashSet
唯一、有序	TreeSet
优先出队	PriorityQueue
多线程 Map	ConcurrentHashMap

小结

• 集合框架两条主线：Collection（List/Set/Queue）和 Map（键值对）
• ArrayList 动态数组（读快），LinkedList 双向链表（增删快）
• HashMap = 数组 + 链表 + 红黑树；负载因子 0.75、2 倍扩容；1.8 改尾插法 + 加红黑树
• HashSet 就是 HashMap 的 key；TreeSet 是红黑树（有序）
• 线程安全用 ConcurrentHashMap / CopyOnWriteArrayList，别用老的 Vector/Hashtable