数据结构基础：集合框架的基石
五种核心数据结构
Java 集合框架建立在五种核心数据结构之上：
| 数据结构 | 时间复杂度 | 特点 | Java 实现 |
|---|---|---|---|
| 数组 | O(1) 随机访问 | 连续内存，CPU 缓存友好 | ArrayList |
| 链表 | O(1) 头尾操作 | 分散内存，动态大小 | LinkedList |
| 哈希表 | O(1) 均摊查找 | 散列分布，快速定位 | HashMap |
| 树 | O(log n) 查找 | 有序，自动平衡 | TreeMap |
| 堆 | O(log n) 堆化 | 优先级队列 | PriorityQueue |
数组 vs 链表
数组：连续内存，下标访问 O(1)
┌───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │
└───┴───┴───┴───┴───┴───┘
链表：分散内存，通过指针连接
┌───┐ ┌───┐ ┌───┐
│ 0 │──▶│ 1 │──▶│ 2 │──▶ null
└───┘ └───┘ └───┘| 操作 | 数组 | 链表 |
|---|---|---|
| 随机访问 | O(1) | O(n) |
| 头部插入 | O(n) | O(1) |
| 尾部插入 | O(1) | O(1) |
| 中间插入 | O(n) | O(n) |
哈希表
通过哈希函数将 key 映射到数组索引：
key = "apple"
hashCode("apple") = 12345678
index = hash & (capacity - 1) = 0~15 之间的某个位置冲突解决：链表（JDK 1.7 头插法 / JDK 1.8+ 尾插法）+ 红黑树（JDK 1.8+，链表过长时转换）。
树与红黑树
普通 BST 可能退化，红黑树保证 O(log n)：
退化的 BST（已排序数据）：
1
\
2
\
3 ← O(n) 查找
红黑树（自动平衡）：
2
/ \
1 3 ← O(log n) 查找TreeMap 底层是红黑树，查找/插入/删除都是 O(log n)。
堆
堆是一种「部分有序」的完全二叉树：
最小堆：
1
/ \
2 3
/ \ / \
4 5 6 7
出堆顺序：1, 2, 3, 4, 5, 6, 7 ← 永远先出最小的PriorityQueue 底层是堆，实现优先级队列。
集合与数据结构对应
| 集合 | 底层数据结构 |
|---|---|
| ArrayList | 动态数组 |
| LinkedList | 双向链表 |
| HashMap | 哈希表 + 链表/红黑树 |
| LinkedHashMap | HashMap + 双向链表 |
| TreeMap | 红黑树 |
| HashSet | HashMap |
| LinkedHashSet | LinkedHashMap |
| TreeSet | TreeMap |
| PriorityQueue | 堆 |
总结
| 要点 | 说明 |
|---|---|
| 数组 | 随机访问最快，插入删除需移动元素 |
| 链表 | 头尾操作最快，随机访问需遍历 |
| 哈希表 | O(1) 查找，但需处理冲突 |
| 红黑树 | O(log n) 查找，有序 |
| 堆 | 优先级队列，最值操作 O(1) |