集合框架体系结构：一张图搞清楚
先看全局
Java 集合框架（Java Collections Framework）是一套统一的接口和实现，解决了「怎么存储、怎么查找、怎么遍历」三大问题。
整个体系可以分成两大部分：单列集合（Collection） 和 双列映射（Map）。
Iterable
│
└── Collection
│
├── List（有序、可重复）
│ ├── ArrayList ← 数组，随机访问快
│ ├── LinkedList ← 链表，头尾操作快
│ ├── Vector ← 同步版 ArrayList（已过时）
│ └── Stack ← 栈，继承 Vector（已过时）
│
├── Set（无序、不可重复）
│ ├── HashSet ← 哈希表，去重最快
│ ├── LinkedHashSet ← 哈希表+链表，保持插入顺序
│ └── TreeSet ← 红黑树，自动排序
│
└── Queue（队列）
├── LinkedList ← 可做队列
├── PriorityQueue ← 优先级队列
└── Deque ← 双端队列
└── ArrayDeque ← 数组实现，比 LinkedList 快
Map（键值对映射，键不可重复）
├── HashMap ← 哈希表，最常用
├── LinkedHashMap ← 哈希表+链表，保持插入顺序
├── TreeMap ← 红黑树，按键排序
├── Hashtable ← 同步版 HashMap（已过时）
└── WeakHashMap ← 弱引用 Map核心接口：为什么这么设计
理解接口设计，才能理解为什么集合这么用。
Collection 接口
所有单列集合的祖宗接口，定义了集合的通用操作：
java
public interface Collection<E> extends Iterable<E> {
// 基本操作
int size();
boolean isEmpty();
boolean contains(Object o);
boolean add(E e); // 添加，成功返回 true
boolean remove(Object o);
// 批量操作
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c); // 取交集
void clear();
// 数组转换
Object[] toArray();
<T> T[] toArray(T[] a);
// 继承自 Iterable：Iterator<E> iterator()
}List 接口
有序、可重复，增加「按位置访问」的能力：
java
public interface List<E> extends Collection<E> {
// 位置访问
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
// 搜索
int indexOf(Object o);
int lastIndexOf(Object o);
// List 特有
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
}Set 接口
无序、不可重复。Set 没有自己定义新方法，它是通过「语义约束」来区分的——Set 的 add 方法会拒绝重复元素：
java
public interface Set<E> extends Collection<E> {
// 继承 Collection，但语义不同：
// - 不能包含重复元素
// - 最多包含一个 null（具体实现决定）
}Map 接口
独立的键值对映射，键不能重复：
java
public interface Map<K, V> {
// 基本操作
int size();
boolean isEmpty();
V get(Object key);
V put(K key, V value);
V remove(Object key);
// 批量操作
void putAll(Map<? extends K, ? extends V> m);
void clear();
// 查询
boolean containsKey(Object key);
boolean containsValue(Object value);
// 视图（返回的集合受原 Map 影响）
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
// Entry：键值对
interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
}
}一个小问题
Map 不是继承自 Collection，因为 Map 是「键值对」而不是「单列元素」。但 Map 提供了 keySet()、values()、entrySet() 三个视图，可以转换成 Collection 来处理。
实现类对比：一张表说清楚
List 实现类
| 实现类 | 底层结构 | 线程安全 | 随机访问 | 适用场景 |
|---|---|---|---|---|
| ArrayList | 动态数组 | 否 | O(1) | 随机访问多，增删少 |
| LinkedList | 双向链表 | 否 | O(n) | 头尾操作多 |
| Vector | 动态数组 | 是（synchronized） | O(1) | 遗留代码，不推荐 |
| Stack | 数组（继承 Vector） | 是 | O(1) | 遗留代码，用 ArrayDeque 替代 |
Set 实现类
| 实现类 | 底层结构 | 元素顺序 | 适用场景 |
|---|---|---|---|
| HashSet | 哈希表 | 无序 | 通用去重 |
| LinkedHashSet | 哈希表+双向链表 | 插入顺序 | 去重且需保持顺序 |
| TreeSet | 红黑树 | 自然排序/自定义 | 需要排序 |
Map 实现类
| 实现类 | 底层结构 | 键顺序 | 线程安全 | 适用场景 |
|---|---|---|---|---|
| HashMap | 哈希表 | 无序 | 否 | 通用键值存储 |
| LinkedHashMap | 哈希表+链表 | 插入顺序 | 否 | 需要保持插入顺序 |
| TreeMap | 红黑树 | 排序 | 否 | 需要按键排序 |
| Hashtable | 哈希表 | 无序 | 是（synchronized） | 遗留代码，不推荐 |
| ConcurrentHashMap | 分段锁哈希表 | 无序 | 是 | 高并发场景 |
演进历史：为什么 HashMap 最常用
JDK 1.0: Vector, Hashtable ← 同步版本，但性能差
JDK 1.2: 引入 Collections 框架，ArrayList, HashMap ← 非同步，高性能
JDK 5.0: 并发包（java.util.concurrent）← ConcurrentHashMap 等
JDK 7: HashMap 使用数组+链表
JDK 8+: HashMap 引入红黑树（链表过长时转化）为什么 Vector/Hashtable 没人用了？因为「同步」不等于「高性能」。对一个已经有锁的 Vector 并发写入，还是在排队，只是把单线程的锁换成了多线程的锁。而 ConcurrentHashMap 的分段锁（或 JDK 8+ 的 CAS + synchronized）允许真正的并发。
选择决策树
需要什么数据结构？
│
├── 单列（一个一个的元素）
│ │
│ ├── 需要有序、可重复 → List
│ │ ├── 随机访问多（遍历/下标访问）→ ArrayList
│ │ ├── 头尾操作多（队列/栈）→ LinkedList / ArrayDeque
│ │ └── 读多写少并发→ CopyOnWriteArrayList
│ │
│ ├── 需要无序、不可重复 → Set
│ │ ├── 通用去重 → HashSet
│ │ ├── 保持插入顺序 → LinkedHashSet
│ │ ├── 需要排序 → TreeSet
│ │ └── 并发去重 → CopyOnWriteArraySet
│ │
│ └── 需要排队 → Queue
│ ├── 优先级 → PriorityQueue
│ ├── 两端操作 → Deque → ArrayDeque（推荐）
│ └── 高并发 → ConcurrentLinkedQueue
│
└── 双列（键值对） → Map
├── 通用键值存储 → HashMap
├── 保持插入顺序 → LinkedHashMap
├── 需要按键排序 → TreeMap
├── 高并发 → ConcurrentHashMap
└── 缓存（自动清理）→ WeakHashMap