面试被问"HashMap 为什么能 O(1)？扩容为什么是 2 倍？JDK 1.8 到底改了什么？"——八股背得滚瓜烂熟，但被追问一句"那它凭什么 O(1)，什么时候会退化"就卡壳。后来真遇到一次线上事故：有人故意构造了一批 hashCode 全部相同的 key，全都挤进 HashMap 同一个格子里，查询从秒回变成卡顿——慢了一百倍。这篇把集合框架从整体结构到 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)（改指针）
内存	连续、紧凑	每个节点多存前后指针

实测差距（10 万元素，随机位置 get）：

ArrayList  随机 get 100 万次：19 ms
LinkedList 随机 get   1 万次：310 ms

同样一次随机访问，LinkedList 比 ArrayList 慢约 1600 倍——O(1) vs O(n) 不是纸面复杂度，是真实 3 个数量级的差距。

选型原则：读多写少用 ArrayList，频繁在头部/中间增删用 LinkedList。绝大多数业务场景 ArrayList 就够。

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

三、HashMap 核心原理（重点）

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

HashMap 本质是一张哈希表——一个数组（叫桶 bucket），每个位置可以挂链表（冲突少时），冲突太多会转红黑树：

• 存数据时，先对 key 做哈希（hashCode() 扰动），用 (n-1) & hash 算出落在数组哪个位置（为什么用 & 不用 %：数组长度是 2 的幂，(n-1) & hash 等价于取模，但位运算快得多）
• 冲突少 → 链表；链表太长（>8 且数组 ≥ 64）→ 转红黑树，查询 O(n) 退化回 O(log n)

3.2 put 的完整流程

1. 数组为空 → 先 resize() 初始化（容量 16）
2. 定位到的桶为空 → 直接放（O(1)，绝大多数情况）
3. 桶有值 → 遍历链表/树：key 相同覆盖 value，否则追加
4. 追加后链表长度 > 8 且数组 ≥ 64 → 链表转红黑树

3.3 扩容：负载因子 0.75、2 倍扩容

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

实测扩容（反射看内部数组长度）：

初始：null（懒加载，没放数据不开内存）
插入 13 个后：32（16×0.75=12，第 13 个触发扩容）
塞 50 个 key 后：128（16 → 32 → 64 → 128）

3.4 树化实测：哈希冲突攻击

实测（构造 hashCode 恒为 1 的 key，全撞一个桶）：

塞 50 个正常 key 后数组长度：128
再放 9 个冲突 key 后的桶类型：TreeNode（链表 → 红黑树）

这就是"哈希冲突攻击"的原理：恶意构造大量 hashCode 相同的 key，让 HashMap 退化成链表（O(n)）。JDK 1.8 的红黑树就是防这个的——冲突再多，查询也只会退化到 O(log n) 而不是 O(n)。

3.5 JDK 1.7 vs 1.8 的变化

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

关键两点：

1. 1.7 头插法有 bug：多线程并发扩容时，头插法会让链表成环，get 直接死循环（CPU 100%）。1.8 改成尾插法解决了死循环——但注意，HashMap 本身依然不是线程安全的，多线程场景要用 ConcurrentHashMap。
2. 为什么加红黑树：就是 3.4 说的哈希冲突攻击防护。

3.6 一句话记住 HashMap

数组解决"定位快"（O(1)），链表/红黑树解决"哈希冲突"（防退化），扩容（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 双向链表（增删快）——实测随机访问差 1600 倍
• HashMap = 数组 + 链表 + 红黑树；负载因子 0.75、2 倍扩容；1.8 改尾插法 + 加红黑树（防哈希冲突攻击）
• HashSet 就是 HashMap 的 key；TreeSet 是红黑树（有序）
• 线程安全用 ConcurrentHashMap / CopyOnWriteArrayList，别用老的 Vector/Hashtable

HashMap 的并发版 ConcurrentHashMap 为什么高效，见《Java 并发编程》；对象的 hashCode/equals 契约（HashMap 为什么要求重写 hashCode）见《Java 面向对象》。

验证说明：HashMap 扩容（13 个触发 16→32、50 个 →128）、树化（9 个冲突 key 桶变 TreeNode）、ArrayList vs LinkedList 随机访问性能对比（100 万次 19ms vs 1 万次 310ms）全部 javac/java 本地实测（--add-opens java.base/java.util=ALL-UNNAMED 反射看内部结构）。