集合框架的整体架构
Iterable：根接口，表示可迭代，所有集合都实现它，因此可以使用
for-each循环。
Iterable (接口)
│
├── Collection (接口) — 存储单元素
│ ├── List (接口) — 有序、可重复、有索引
│ │ ├── ArrayList
│ │ ├── LinkedList
│ │ ├── Vector (线程安全)
│ │ └── Stack (继承自Vector)
│ ├── Set (接口) — 无序、不可重复
│ │ ├── HashSet
│ │ ├── LinkedHashSet (保持插入顺序)
│ │ ├── TreeSet (排序)
│ └── Queue (接口) / Deque (接口) — 队列/双端队列
│ ├── PriorityQueue (优先级队列)
│ └── ArrayDeque (双端队列)
│
└── Map (接口) — 存储键值对，键不可重复
├── HashMap
├── LinkedHashMap (保持插入或访问顺序)
├── TreeMap (按键排序)
├── Hashtable (线程安全，不推荐)
└── ConcurrentHashMap (线程安全，高并发)ArrayList
动态数组实现类，位于
java.util包中，提供了可调整大小的数组，支持随机访问
- 动态扩容：初始容量为 10，当元素超过容量时自动增加（扩容约 1.5 倍）
- 有序：保持元素的插入顺序
- 允许 null：可以存储多个
null值 - 允许重复：基于索引存储，不自动去重
- 非线程安全：多线程环境下需要外部同步（可使用
Collections.synchronizedList或CopyOnWriteArrayList）
构造方法
ArrayList() // 默认容量 10
ArrayList(int initialCapacity) // 指定初始容量
ArrayList(Collection<? extends E> c) // 用已有集合初始化核心方法
ArrayList<String> list = new ArrayList<>();
// 增
list.add("A"); // 尾部添加
list.add(0, "B"); // 指定位置插入
list.addAll(Arrays.asList("C", "D")); // 批量添加
// 删
list.remove(1); // 按索引删除
list.remove("A"); // 按对象删除（第一个匹配）
list.clear(); // 清空
// 改
list.set(0, "X");
// 查
String s = list.get(0); // 随机访问 O(1)
int index = list.indexOf("X");
boolean exists = list.contains("X");
// 大小
int size = list.size();
boolean empty = list.isEmpty();
// 遍历
for (String item : list) { } // for-each
for (int i = 0; i < list.size(); i++) { } // 索引
list.forEach(System.out::println); // Lambda
Iterator<String> it = list.iterator(); // 迭代器- 遍历时删除：使用
Iterator.remove()或removeIf，避免ConcurrentModificationException - 初始容量预估：如果已知元素数量，指定初始容量可减少扩容开销
- 转换为数组：
list.toArray(new String[0])或list.toArray(T[]::new)（Java 11+） - 性能优化：频繁插入/删除中间元素时考虑
LinkedList；频繁随机访问则用ArrayList
LinkedList
双向链表实现，位于
java.util包，同时实现了List和Deque接口，可以作为列表使用，也可以作为双端队列（栈/队列）使用
- 底层结构：双向链表（每个节点包含前驱、后继指针和元素值）
- 有序：保持元素的插入顺序
- 允许 null：可以存储多个
null值 - 允许重复：不自动去重
- 非线程安全：多线程环境下需外部同步（或使用
Collections.synchronizedList） - 无容量限制：不需要扩容，按需分配节点
- 内存开销：每个元素额外存储两个指针（prev/next）
构造方法
LinkedList<String> list = new LinkedList<>(); // 空链表
LinkedList<String> list = new LinkedList<>(Collection<? extends E> c); // 用集合初始化核心方法
LinkedList<String> list = new LinkedList<>();
// 添加
list.add("A"); // 尾部
list.addFirst("B"); // 头部
list.offerLast("C"); // 尾部（返回值版本）
// 访问
String first = list.getFirst(); // "B"
String last = list.peekLast(); // "C"
// 删除
list.removeFirst(); // 删除头部 "B"
list.poll(); // 删除头部（原 "A"）
// 栈操作
list.push("D"); // 头部插入
String top = list.pop(); // 弹出头部
// 队列操作
list.offer("E");
String head = list.poll(); // 获取并移除头部
// 迭代
for (String s : list) { }
Iterator<String> rev = list.descendingIterator();
while (rev.hasNext()) System.out.println(rev.next());Vector
动态数组实现，位于
java.util包，与 ArrayList 相似，但是线程安全，遗留集合很少使用
- 底层结构：动态数组（和 ArrayList 一样）
- 线程安全：所有方法都同步，可直接在多线程环境下使用
- 扩容机制：可指定扩容增量（capacityIncrement），默认为原容量的 2 倍（ArrayList 为 1.5 倍）
- 有序：保持元素插入顺序
- 允许 null / 重复：支持多个 null 值和重复元素
- 遗留类：在 JDK 1.2 被重构为实现
List接口，但仍被视为“遗留集合”
Stack
遗留的（Legacy）类，位于
java.util包，继承自Vector，后进先出（LIFO）的栈数据结构，已被Deque接口（如ArrayDeque）所取代
- 继承关系：
Stack<E> extends Vector<E>，因此拥有 Vector 的所有特性（包括线程安全的方法同步）。 - LIFO 行为：提供标准的栈操作：
push（压栈）、pop（弹栈）、peek（查看栈顶）。 - 线程安全：由于继承自
Vector，所有方法都是synchronized的，可直接在多线程环境下使用（但锁粒度较粗）。 - 允许 null：可以存储 null 值。
- 有序：保持元素的插入顺序（栈的顺序由压栈时间决定）。
HashSet
Set 接口实现，位于
java.util包，基于HashMap实现，存储不重复的元素，且无序，基本操作（添加、删除、查找）能达到 O(1) 时间复杂度
- 基于 HashMap：内部维护一个
HashMap<E, Object>，元素作为 key 存入，value 是一个固定的占位对象PRESENT。 - 不重复：通过元素的
hashCode()和equals()判断重复，最多包含一个null值。 - 无序：不保证元素的存储顺序，迭代顺序可能与插入顺序不同（甚至在不同 JDK 版本中也不一致）。
- 非线程安全：多线程环境需外部同步，或使用
Collections.synchronizedSet或CopyOnWriteArraySet。 - 允许 null：允许添加一个
null元素（多个null只会保留一个）。 - 快速失败：迭代器采用 fail-fast 机制，并发修改时抛出
ConcurrentModificationException。
构造方法和常用方法
import java.util.*;
public class HashSetSimpleDemo {
public static void main(String[] args) {
// 1. 构造方法
Set<String> set = new HashSet<>(); // 默认容量16
Set<String> set2 = new HashSet<>(32); // 指定初始容量
Set<String> set3 = new HashSet<>(32, 0.8f); // 指定容量+加载因子
Set<Integer> set4 = new HashSet<>(Arrays.asList(1,2,2,3)); // 从集合构造
// 2. 常用方法
set.add("A"); // 添加，成功true，重复false
set.add("B");
set.add("A"); // 重复，返回false
set.contains("A"); // true
set.remove("B"); // true
set.size(); // 1
set.isEmpty(); // false
set.clear(); // 清空
// 3. 遍历
for (String s : set) { }
set.forEach(System.out::println);
// 4. 去重示例
List<Integer> list = Arrays.asList(1,2,2,3);
Set<Integer> unique = new HashSet<>(list); // [1,2,3]
}
}LinkedHashSet
HashSet的子类，位于java.util包，在HashSet的基础上维护了一个双向链表，元素按照插入的顺序返回
- 继承 HashSet：底层复用
HashSet的逻辑，但内部使用LinkedHashMap替代HashMap。 - 有序：维护双向链表，迭代顺序 = 插入顺序（构造时可指定为访问顺序，但极少使用）。
- 不重复：与
HashSet相同，依靠hashCode()和equals()判断重复。 - 允许 null：允许一个 null 元素。
- 非线程安全：需要外部同步（
Collections.synchronizedSet）或使用CopyOnWriteArraySet。 - 性能：比
HashSet略低（维护链表开销），但增删查仍为 O(1)。
构造方法和常用方法
import java.util.*;
public class LinkedHashSetDemo {
public static void main(String[] args) {
// 1. 构造方法
LinkedHashSet<String> set1 = new LinkedHashSet<>(); // 默认容量16
LinkedHashSet<String> set2 = new LinkedHashSet<>(32); // 指定初始容量
LinkedHashSet<String> set3 = new LinkedHashSet<>(32, 0.8f); // 指定容量+加载因子
LinkedHashSet<String> set4 = new LinkedHashSet<>(Arrays.asList("A","B","C")); // 从集合构造
// 2. 常用方法（继承自 HashSet）
set1.add("B"); // 添加
set1.add("A");
set1.add("C");
set1.add("B"); // 重复，忽略
System.out.println(set1); // [B, A, C] 保持插入顺序
set1.contains("A"); // true
set1.remove("B"); // true
set1.size(); // 2
set1.isEmpty(); // false
set1.clear(); // 清空
// 3. 遍历（按插入顺序）
for (String s : set1) { }
set1.forEach(System.out::println);
}
}TreeSet
基于红黑树实现的
Set接口，位于java.util包，保证元素处于排序状态，
- 基于 TreeMap：底层使用
TreeMap存储元素，元素作为 key，value 是一个固定的PRESENT对象。 - 有序：元素按照自然顺序（
Comparable）或构造时指定的Comparator排序。 - 不重复：通过比较器（
compareTo或compare）判断重复，而非equals（但最好保持一致）。 - 不允许 null：JDK 7 以后，
TreeSet不允许添加null元素（因为compare时会抛出NullPointerException）。 - 非线程安全：需要外部同步（
Collections.synchronizedSortedSet）或使用ConcurrentSkipListSet。 - 快速失败：迭代器采用 fail-fast 机制。
构造方法和常用方法
import java.util.*;
public class TreeSetDemo {
public static void main(String[] args) {
// 1. 构造方法
TreeSet<Integer> set1 = new TreeSet<>(); // 自然顺序
TreeSet<Integer> set2 = new TreeSet<>(Comparator.reverseOrder()); // 自定义比较器（降序）
TreeSet<Integer> set3 = new TreeSet<>(Arrays.asList(5,2,8,1,9)); // 从集合构造
// 2. 常用方法
TreeSet<Integer> set = new TreeSet<>();
set.add(5); set.add(2); set.add(8); set.add(1); set.add(9);
System.out.println(set); // [1,2,5,8,9] 自动排序
set.contains(5); // true
set.remove(2); // true
set.size(); // 4
set.first(); // 1
set.last(); // 9
// 子集视图
set.subSet(3, 8); // [5] (包含3, 不包含8)
set.headSet(5); // [1]
set.tailSet(5); // [5,8,9]
// 导航方法
set.lower(5); // 1 (小于5的最大元素)
set.floor(5); // 5 (小于等于5)
set.higher(5); // 8 (大于5的最小元素)
set.ceiling(6); // 8 (大于等于6)
// 删除并获取首/尾
set.pollFirst(); // 1
set.pollLast(); // 9
// 降序视图 / 降序迭代器
set.descendingSet(); // [8,5]
set.descendingIterator();
set.clear(); // 清空
}
}PriorityQueue
基于优先级堆（默认小顶堆）实现的优先级队列，位于
java.util包。实现Queue接口,元素按照自然顺序或提供的Comparator进行排序，队首元素是优先级最高的元素（即最小或最大）
- 基于数组的二叉堆：底层使用动态数组存储元素，逻辑上是一棵完全二叉树（最小堆或最大堆）。
- 无序迭代：
iterator()不保证任何顺序，若需有序遍历，应使用Arrays.sort(pq.toArray())或不断poll()。 - 不允许 null：
null元素不允许，因为比较时会抛出NullPointerException。 - 非线程安全：多线程环境需使用
PriorityBlockingQueue或外部同步。 - 动态扩容：初始容量为 11，当元素数量超过容量时会自动扩容（增长策略为
oldCapacity < 64 ? oldCapacity+2 : oldCapacity>>1约 1.5 倍）。 - 不保证相等元素的顺序：如果多个元素优先级相同（比较器返回 0），则不保证它们之间的相对顺序。
- 时间复杂度：入队和出队操作均为 O(log n)，获取队首 O(1)。
构造方法与常用方法
import java.util.*;
public class PriorityQueueDemo {
public static void main(String[] args) {
// 1. 构造方法
PriorityQueue<Integer> pq1 = new PriorityQueue<>(); // 默认容量11，小顶堆
PriorityQueue<Integer> pq2 = new PriorityQueue<>(20); // 指定初始容量
PriorityQueue<Integer> pq3 = new PriorityQueue<>(Comparator.reverseOrder()); // 大顶堆
PriorityQueue<Integer> pq4 = new PriorityQueue<>(Arrays.asList(5,1,3,2)); // 从集合构造
// 2. 常用方法
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); // 入队（推荐）
pq.offer(1);
pq.offer(3);
pq.add(2); // 同 offer
System.out.println(pq); // [1, 2, 3, 5] ？迭代顺序不保证，实际可能是 [1,2,3,5]
pq.peek(); // 1（获取队首不删除）
pq.poll(); // 1（出队，删除队首）
pq.poll(); // 2
pq.size(); // 2
pq.isEmpty(); // false
pq.contains(3); // true（线性扫描 O(n)）
pq.remove(3); // 删除指定元素（O(n)）
pq.clear(); // 清空
// 大顶堆示例
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(3);
System.out.println(maxHeap.poll()); // 5
}
}ArrayDeque
基于循环数组的双端队列，实现了
Deque接口。可作为队列（FIFO）或栈（LIFO）使用，性能优于LinkedList和Stack。
- 底层结构：循环数组，
head/tail指针。 - 容量动态扩容：容量总是 2 的幂，扩容时翻倍。
- 不允许
null：添加null会抛NullPointerException。 - 非线程安全。
- 时间复杂度：头尾操作 O(1)，其余线性操作 O(n)。
构造方法与常用方法
// 构造方法
ArrayDeque<String> d1 = new ArrayDeque<>(); // 初始容量 16
ArrayDeque<String> d2 = new ArrayDeque<>(32); // 指定容量（会调整为2的幂）
ArrayDeque<String> d3 = new ArrayDeque<>(List.of("A","B"));
// 常用方法
ArrayDeque<String> dq = new ArrayDeque<>();
dq.addFirst("A"); // 头部添加
dq.addLast("B"); // 尾部添加
dq.offerFirst("C"); // 头部添加（返回boolean）
dq.offerLast("D"); // 尾部添加
dq.getFirst(); // 获取头部（不删，空抛异常）
dq.peekFirst(); // 获取头部（不删，空返回null）
dq.removeFirst(); // 移除头部（空抛异常）
dq.pollFirst(); // 移除头部（空返回null）
dq.pollLast(); // 移除尾部
// 作为栈
dq.push("X"); // 压栈 → addFirst
String top = dq.pop(); // 弹栈 → removeFirst
// 作为队列
dq.offer("E"); // 入队 → addLast
String head = dq.poll(); // 出队 → pollFirst
// 遍历
for (String s : dq) { }
dq.forEach(System.out::println);HashMap
基于哈希表的
Map实现，存储键值对，键不可重复。最常用的Map。
- 底层：数组 + 链表/红黑树（JDK 8+，链表长度 >8 转为红黑树）。
- 允许一个
null键和多个null值。 - 无序：不保证迭代顺序（与
HashSet一致）。 - 非线程安全。
- 时间复杂度：
get/putO(1)（理想），O(log n)（红黑树退化）。 - 初始容量 16，加载因子 0.75，扩容翻倍。
构造方法与常用方法
// 构造方法
Map<String,Integer> map1 = new HashMap<>(); // 默认容量16
Map<String,Integer> map2 = new HashMap<>(32); // 指定容量
Map<String,Integer> map3 = new HashMap<>(32, 0.8f); // 容量+加载因子
Map<String,Integer> map4 = new HashMap<>(Map.of("A",1,"B",2)); // 从已有Map构造
// 常用方法
Map<String,Integer> map = new HashMap<>();
map.put("A", 1); // 添加/修改
map.putIfAbsent("B", 2); // 不存在才添加
map.get("A"); // 获取，不存在返回 null
map.getOrDefault("C", 0); // 获取，不存在返回默认值
map.containsKey("A"); // true
map.containsValue(2); // true
map.remove("A"); // 删除键，返回值
map.remove("B", 2); // 键值匹配才删除
map.replace("B", 3); // 替换
map.size(); // 大小
map.isEmpty(); // 判空
map.keySet(); // 返回所有键的Set
map.values(); // 返回所有值的Collection
map.entrySet(); // 返回所有Entry的Set
// 遍历
for (Map.Entry<String,Integer> e : map.entrySet()) {
System.out.println(e.getKey() + "=" + e.getValue());
}
map.forEach((k,v) -> System.out.println(k + "=" + v));LinkedHashMap
HashMap的子类，维护双向链表记录插入顺序（或访问顺序）。
- 继承
HashMap，底层使用LinkedHashMap.Entry（继承HashMap.Node，多了 before/after）。 - 有序：迭代顺序 = 插入顺序（默认）或访问顺序（构造时指定
accessOrder=true）。 - 允许
null键值。 - 非线程安全。
- 性能：略低于
HashMap（维护链表开销），但基本操作仍为 O(1)。
构造方法与常用方法
// 构造方法（默认插入顺序）
LinkedHashMap<String,Integer> map = new LinkedHashMap<>();
// 指定访问顺序（LRU 缓存常用）
LinkedHashMap<String,Integer> lru = new LinkedHashMap<>(16, 0.75f, true);
// 用法与 HashMap 完全相同，但迭代顺序固定
map.put("B", 2);
map.put("A", 1);
map.put("C", 3);
System.out.println(map.keySet()); // [B, A, C] 插入顺序
// 访问顺序模式下，get 会将元素移到末尾
lru.put(1, "v1");
lru.put(2, "v2");
lru.get(1); // 将键 1 移到末尾
// 此时顺序：2 → 1TreeMap
基于红黑树的
Map实现，键按自然顺序或Comparator排序。
- 底层：红黑树（
TreeMap是TreeSet的底层依赖）。 - 键有序：支持
firstKey()、lastKey()、subMap()等导航方法。 - 不允许
null键（JDK 7+），但值可以为null。 - 非线程安全。
- 时间复杂度：
put/get/removeO(log n)。
构造方法与常用方法
// 构造方法
TreeMap<String,Integer> map1 = new TreeMap<>(); // 自然顺序
TreeMap<String,Integer> map2 = new TreeMap<>(Comparator.reverseOrder());// 自定义比较器
TreeMap<String,Integer> map3 = new TreeMap<>(Map.of("A",1,"B",2)); // 从已有Map
// 常用方法（继承自 Map）
TreeMap<String,Integer> map = new TreeMap<>();
map.put("B",2);
map.put("A",1);
map.put("C",3);
System.out.println(map); // {A=1, B=2, C=3} 按key排序
map.firstKey(); // A
map.lastKey(); // C
map.lowerKey("B"); // A (小于B的最大键)
map.higherKey("B"); // C
map.subMap("A","C"); // {A=1, B=2} [A, C)
map.headMap("B"); // {A=1}
map.tailMap("B"); // {B=2, C=3}Hashtable
遗留类，线程安全的哈希表，已被
HashMap和ConcurrentHashMap取代。
- 线程安全：所有方法都
synchronized。 - 不允许
null键或值（与HashMap不同）。 - 初始容量 11，扩容为
2*old+1。 - 不推荐使用：单线程用
HashMap，多线程用ConcurrentHashMap。
构造方法与常用方法
Hashtable<String,Integer> table = new Hashtable<>();
table.put("A", 1); // 不能 put(null, anything)
table.get("A");
table.remove("A");
// 迭代器需要手动同步（但一般不直接用了）ConcurrentHashMap
高并发环境下使用的线程安全哈希表，性能远优于
Hashtable。
- JDK 1.5+，采用分段锁（JDK 7）或 CAS + synchronized（JDK 8+，锁粒度更细）。
- 不允许
null键或值。 - 读操作无锁，写操作只锁当前桶（或红黑树）。
- 迭代器弱一致性：不抛
ConcurrentModificationException，但可能不反映最新修改。 - 推荐：多线程环境下替代
Hashtable和Collections.synchronizedMap。
构造方法与常用方法
ConcurrentHashMap<String,Integer> map = new ConcurrentHashMap<>();
map.put("A", 1);
map.get("A");
map.remove("A");
// 原子操作
map.putIfAbsent("B", 2);
map.computeIfAbsent("C", k -> k.length());
// 遍历（弱一致性，允许并发修改）
map.forEach((k,v) -> System.out.println(k + "=" + v));