言不信者行不果，行不敏者言多滞.

4. 集合类

4.1 集合类概述

4.1.1 集合框架遵循原则

4.1.2 集合框架体系

4.2 核心接口和实现类解析

4.2.1 Collection 接口体系

4.2.1.1 Collection 接口核心定义

4.2.1.2 List接口详解

4.2.1.3 Set 接口详解

4.2.1.4 Queue/Deque接口详解

4.2.2 Map 接口体系详解

4.3 集合类选择

4.3.1 集合类选择指南

4.3.2 集合类选择决策树

4.4 性能优化建议

4.5 总结

续前篇：编程语言Java——核心技术篇（三）异常处理详解-CSDN博客

4. 集合类

Java集合框架(Java Collections Framework, JCF)是Java语言中用于存储和操作数据集合的一组接口和类。它提供了一套标准化的数据结构实现，使开发者能够高效地处理数据。

4.1 集合类概述

4.1.1 集合框架遵循原则

集合框架的设计遵循了几个重要原则：

接口与实现分离：所有具体集合类都实现自标准接口（如List、Set、Map），这使得程序可以灵活切换不同的实现而不影响业务逻辑。
算法复用：Collections工具类提供了大量通用算法（如排序、查找、反转等），这些算法可以应用于任何实现了相应接口的集合类。
性能优化：针对不同使用场景提供了多种实现，如需要快速随机访问选择ArrayList，需要频繁插入删除选择LinkedList。
扩展性：通过迭代器模式（Iterator）和比较器（Comparator）等设计，使集合框架易于扩展和定制。
类型安全：通过泛型机制在编译期检查类型一致性，避免了运行时的类型转换错误。

4.1.2 集合框架体系

这张图很清楚了，两个顶级父类接口Iterable和Map，剩下的List，Set和Queue等都是两个接口的实现子接口，在下来才是各种实现类。如果只但看各个接口之间的继承关系还有下面这张图：

我感觉这两个图可以详细地记一下，因为适用性挺广的，存放数据和操作都会频繁地遇到集合类。

4.2 核心接口和实现类解析

4.2.1 Collection 接口体系

4.2.1.1 Collection 接口核心定义

Collection是单列集合的根接口，定义了集合的通用行为：

public interface Collection<E> extends Iterable<E> {// 基本操作int size();boolean isEmpty();boolean contains(Object o);Iterator<E> iterator();Object[] toArray();<T> T[] toArray(T[] a);// 修改操作boolean add(E e);boolean remove(Object o);// 批量操作boolean containsAll(Collection<?> c);boolean addAll(Collection<? extends E> c);boolean removeAll(Collection<?> c);boolean retainAll(Collection<?> c);void clear();// Java 8新增boolean removeIf(Predicate<? super E> filter);Spliterator<E> spliterator();Stream<E> stream();Stream<E> parallelStream();
}

4.2.1.2 List接口详解

1. 核心特性：

有序集合：元素按插入顺序存储，可通过索引精确访问
元素可重复：允许存储相同元素（包括null）
位置访问：提供基于索引的增删改查方法

特有方法：

// 位置访问
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<E> subList(int fromIndex, int toIndex);// Java 8新增
default void replaceAll(UnaryOperator<E> operator);
default void sort(Comparator<? super E> c);

2. 实现类对比

对比维度	ArrayList	LinkedList	Vector
底层数据结构	动态数组	双向链表	动态数组
内存布局	连续内存空间	离散节点存储	连续内存空间
初始容量	10 (首次添加时初始化)	无固定容量概念	10
扩容机制	1.5倍增长 (int newCapacity = oldCapacity + (oldCapacity >> 1))	无需扩容，动态增加节点	2倍增长 (capacityIncrement>0时按指定值增长)
随机访问性能	O(1) - 直接数组索引访问	O(n) - 需要遍历链表	O(1)
头部插入性能	O(n) - 需要移动所有元素	O(1) - 修改头节点引用	O(n)
尾部插入性能	O(1)摊销 (考虑扩容)	O(1) - 修改尾节点引用	O(1)
中间插入性能	O(n) - 平均需要移动一半元素	O(n) - 需要先找到位置	O(n)
删除操作性能	O(n) - 类似插入	O(1) - 找到节点后只需修改引用	O(n)
内存占用	较少 (仅需存储元素和数组引用)	较高 (每个元素需要额外前后节点引用)	与ArrayList类似
缓存友好性	好 (空间局部性原理)	差	好
线程安全性	非线程安全	非线程安全	线程安全 (方法级synchronized)
迭代器安全性	快速失败 (fail-fast)	快速失败	线程安全但迭代时仍需外部同步
序列化支持	自定义序列化 (transient数组+size)	自定义序列化	同ArrayList
最佳适用场景	读多写少，随机访问频繁	写多读少，频繁在头尾操作	需要线程安全的场景 (已过时)

3. ArrayList 示例

// 创建ArrayList
List<String> arrayList = new ArrayList<>();// 添加元素
arrayList.add("Java");
arrayList.add("Python");
arrayList.add(1, "C++"); // 在指定位置插入// 访问元素
String lang = arrayList.get(0); // "Java"// 遍历方式1：for循环
for (int i = 0; i < arrayList.size(); i++) {System.out.println(arrayList.get(i));
}// 遍历方式2：增强for循环
for (String language : arrayList) {System.out.println(language);
}// 遍历方式3：迭代器
Iterator<String> it = arrayList.iterator();
while (it.hasNext()) {System.out.println(it.next());
}// 删除元素
arrayList.remove("Python"); // 按对象删除
arrayList.remove(0);       // 按索引删除// 转换为数组
String[] array = arrayList.toArray(new String[0]);// Java 8操作
arrayList.removeIf(s -> s.length() < 3); // 删除长度小于3的元素
arrayList.replaceAll(String::toUpperCase); // 全部转为大写

ArrayList常用的方法都在这里了。我们可以把ArrayList就看成一个动态数组，实际上ArrayList比较适合查询数组内地各个元素，但在增删改上地性能较差。

4. LinkedList 示例

// 创建LinkedList
LinkedList<String> linkedList = new LinkedList<>();// 添加元素
linkedList.add("Apple");
linkedList.addFirst("Banana"); // 添加到头部
linkedList.addLast("Orange"); // 添加到尾部
linkedList.add(1, "Grape");   // 在指定位置插入// 队列操作
linkedList.offer("Pear");     // 添加到队尾
String head = linkedList.poll(); // 移除并返回队头// 栈操作
linkedList.push("Cherry");    // 压栈
String top = linkedList.pop(); // 弹栈// 获取元素
String first = linkedList.getFirst();
String last = linkedList.getLast();// 遍历方式：降序迭代器
Iterator<String> descIt = linkedList.descendingIterator();
while (descIt.hasNext()) {System.out.println(descIt.next());
}

这里刻意强调一下栈操作。LinkedList 实现了 Deque（双端队列）接口，因此可以作为栈(Stack)使用。栈是一种后进先出(LIFO)的数据结构，实际上就是数据接口的知识。

// 将元素推入栈顶（实际添加到链表头部）入栈
LinkedList<String> stack = new LinkedList<>();
stack.push("A");  // 栈底 ← "A" → 栈顶
stack.push("B");  // 栈底 ← "A" ← "B" → 栈顶
stack.push("C");  // 栈底 ← "A" ← "B" ← "C" → 栈顶String top = stack.pop();  // 移除并返回栈顶元素 "C" 出栈
// 现在栈状态：栈底 ← "A" ← "B" → 栈顶String peek = stack.peek(); // 返回 "B"（栈顶元素）
// 栈保持不变：栈底 ← "A" ← "B" → 栈顶

4.2.1.3 Set 接口详解

1. 核心特性：

元素唯一性：不包含重复元素（依据equals()判断）
无序性：不保证维护插入顺序（TreeSet/LinkedHashSet除外）
数学集合：支持并集、交集、差集等操作

2. 实现类对比

对比维度	HashSet	LinkedHashSet	TreeSet
底层实现	基于HashMap	继承HashSet，使用LinkedHashMap	基于TreeMap
数据结构	哈希表+链表/红黑树	哈希表+链表+双向链表	红黑树
元素顺序	无序	插入顺序	自然顺序/Comparator定义顺序
null值支持	允许一个null元素	允许一个null元素	不允许null元素
基本操作复杂度	平均O(1)	平均O(1)	O(log n)
内存开销	较低	较高 (额外维护双向链表)	较高 (树结构开销)
构造方法	可指定初始容量和负载因子	同HashSet	可提供Comparator
迭代顺序	不稳定	插入顺序稳定	排序顺序稳定
性能特点	插入删除极快	插入删除稍慢于HashSet	插入删除较慢但有序
额外方法	无	无	提供first(), last(), subSet()等导航方法
线程安全性	非线程安全	非线程安全	非线程安全
哈希冲突解决	链地址法，JDK8后链表转红黑树	同HashSet	不适用
扩容机制	默认16→32→64... 负载因子0.75	同HashSet	无需扩容
比较方式	equals()和hashCode()	同HashSet	Comparable或Comparator
典型应用场景	需要快速判断元素是否存在	需要保持插入顺序的集合	需要有序集合或范围查询

3. HashSet 示例

// 创建HashSet
Set<String> hashSet = new HashSet<>();// 添加元素
hashSet.add("Java");
hashSet.add("Python");
hashSet.add("Java"); // 重复元素不会被添加// 判断包含
boolean hasJava = hashSet.contains("Java"); // true// 删除元素
hashSet.remove("Python");// 遍历
for (String language : hashSet) {System.out.println(language);
}// 集合运算
Set<String> otherSet = new HashSet<>(Arrays.asList("C++", "Java", "JavaScript"));hashSet.retainAll(otherSet); // 交集
hashSet.addAll(otherSet);    // 并集
hashSet.removeAll(otherSet); // 差集

4. LinkedHashSet示例

// 创建LinkedHashSet（保持插入顺序）
Set<String> linkedHashSet = new LinkedHashSet<>();linkedHashSet.add("First");
linkedHashSet.add("Second");
linkedHashSet.add("Third");// 遍历顺序与插入顺序一致
for (String item : linkedHashSet) {System.out.println(item); // 输出顺序：First, Second, Third
}// 移除并添加，顺序会变
linkedHashSet.remove("Second");
linkedHashSet.add("Second");// 现在顺序：First, Third, Second

LinkedHashSet能够保持插入顺序，即删除时后面元素会自动补位，增添元素时会自动退位；但HashSet不会，不管组内元素如何变化，其他元素均不变。

5. TreeSet示例

// 创建TreeSet（自然排序）
Set<String> treeSet = new TreeSet<>();treeSet.add("Orange");
treeSet.add("Apple");
treeSet.add("Banana");// 自动排序输出
for (String fruit : treeSet) {System.out.println(fruit); // Apple, Banana, Orange
}// 定制排序
Set<Integer> customSort = new TreeSet<>((a, b) -> b - a); // 降序
customSort.addAll(Arrays.asList(5, 3, 9, 1));// 输出：9, 5, 3, 1// 导航方法
TreeSet<Integer> nums = new TreeSet<>(Arrays.asList(1, 3, 5, 7, 9));Integer lower = nums.lower(5);  // 3 (小于5的最大元素)
Integer higher = nums.higher(5); // 7 (大于5的最小元素)
Integer floor = nums.floor(4);   // 3 (小于等于4的最大元素)
Integer ceiling = nums.ceiling(6); // 7 (大于等于6的最小元素)// 范围视图
Set<Integer> subSet = nums.subSet(3, true, 7, false); // [3, 5]

4.2.1.4 Queue/Deque接口详解

1. Queue核心方法：

操作类型	抛出异常的方法	返回特殊值的方法
插入	add(e)	offer(e)
移除	remove()	poll()
检查	element()	peek()

2. 实现类对比

对比维度	PriorityQueue	ArrayDeque	LinkedList
底层结构	二叉堆(数组实现)	循环数组	双向链表
排序特性	自然顺序/Comparator	无	无
容量限制	无界(自动扩容)	可选有界(默认16)	无界
null值允许	不允许	不允许	允许
基本操作复杂度	插入O(log n)，获取O(1)	两端操作O(1)	两端操作O(1)，中间操作O(n)
线程安全性	非线程安全	非线程安全	非线程安全
内存使用	紧凑(数组)	非常紧凑	较高(节点开销)
扩容策略	小规模+50%，大规模+25%	双倍增长	动态增加节点
迭代顺序	按优先级顺序	FIFO/LIFO顺序	插入顺序
特殊方法	comparator()	无	大量列表操作方法
最佳适用场景	任务调度，需要自动排序	高性能栈/队列实现	需要同时作为队列和列表使用
实现接口	Queue	Deque	List, Deque

3. PriorityQueue示例

// 创建优先级队列（自然排序）
PriorityQueue<Integer> pq = new PriorityQueue<>();pq.add(30);
pq.add(10);
pq.add(20);// 取出时会按顺序
while (!pq.isEmpty()) {System.out.println(pq.poll()); // 10, 20, 30
}// 定制排序
PriorityQueue<String> customPq = new PriorityQueue<>((s1, s2) -> s2.length() - s1.length()); // 按长度降序customPq.add("Apple");
customPq.add("Banana");
customPq.add("Pear");// 输出：Banana, Apple, Pear

2. ArrayDeque示例

// 创建ArrayDeque
Deque<String> deque = new ArrayDeque<>();// 作为栈使用
deque.push("First");
deque.push("Second");
String top = deque.pop(); // "Second"// 作为队列使用
deque.offer("Third");
deque.offer("Fourth");
String head = deque.poll(); // "First"// 双端操作
deque.addFirst("Front");
deque.addLast("End");
String first = deque.getFirst(); // "Front"
String last = deque.getLast();   // "End"

4.2.2 Map 接口体系详解

1. 核心定义

public interface Map<K,V> {// 基本操作int size();boolean isEmpty();boolean containsKey(Object key);boolean containsValue(Object value);V get(Object key);V put(K key, V value);V remove(Object key);// 批量操作void putAll(Map<? extends K, ? extends V> m);void clear();// 集合视图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);// Java 8新增boolean equals(Object o);int hashCode();public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey()// ...}// Java 8新增方法default V getOrDefault(Object key, V defaultValue)default void forEach(BiConsumer<? super K, ? super V> action)default V putIfAbsent(K key, V value)default boolean remove(Object key, Object value)default boolean replace(K key, V oldValue, V newValue)default V replace(K key, V value)default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)// ...
}

这里是Java的源码，可以看到Map实际上放的是一对K-V键值对。

2. 实现类对比

对比维度	HashMap	LinkedHashMap	TreeMap
继承体系	AbstractMap	继承HashMap	AbstractMap
底层结构	数组+链表/红黑树	数组+链表/红黑树+双向链表	红黑树
键值顺序	无序	插入顺序/访问顺序	键的自然顺序/Comparator顺序
null键值支持	允许null键和null值	同HashMap	不允许null键
初始容量	16	同HashMap	无容量概念
扩容机制	2^n增长，负载因子0.75	同HashMap	无需扩容
基本操作复杂度	平均O(1)	平均O(1)	O(log n)
线程安全性	非线程安全	非线程安全	非线程安全
迭代器类型	fail-fast	fail-fast	fail-fast
额外功能	无	可设置访问顺序(LRU实现)	导航方法(如ceilingKey)
哈希算法	(h = key.hashCode()) ^ (h >>> 16)	同HashMap	不适用
树化阈值	链表长度≥8且桶数量≥64	同HashMap	不适用
序列化方式	自定义	同HashMap	同HashMap
推荐场景	大多数键值对存储场景	需要保持插入/访问顺序	需要有序映射或范围查询

3. HashMap示例

// 创建HashMap
Map<String, Integer> hashMap = new HashMap<>();// 添加键值对
hashMap.put("Apple", 10);
hashMap.put("Banana", 20);
hashMap.put("Orange", 15);// 获取值
int apples = hashMap.get("Apple"); // 10
int defaultValue = hashMap.getOrDefault("Pear", 0); // 0// 遍历方式1：entrySet
for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());
}// 遍历方式2：keySet
for (String key : hashMap.keySet()) {System.out.println(key);
}// 遍历方式3：values
for (int value : hashMap.values()) {System.out.println(value);
}// Java 8操作
hashMap.forEach((k, v) -> System.out.println(k + " => " + v));
hashMap.computeIfAbsent("Pear", k -> 5); // 如果不存在则添加
hashMap.merge("Apple", 5, Integer::sum); // Apple数量增加5

4. LinkedHashMap示例

// 创建LinkedHashMap（保持插入顺序）
Map<String, Integer> linkedHashMap = new LinkedHashMap<>();linkedHashMap.put("First", 1);
linkedHashMap.put("Second", 2);
linkedHashMap.put("Third", 3);// 遍历顺序与插入顺序一致
linkedHashMap.forEach((k, v) -> System.out.println(k)); // First, Second, Third// 按访问顺序排序的LinkedHashMap（可用于LRU缓存）
Map<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);accessOrderMap.put("One", 1);
accessOrderMap.put("Two", 2);
accessOrderMap.put("Three", 3);accessOrderMap.get("Two"); // 访问Two会使它移动到末尾// 现在顺序：One, Three, Two

5. TreeMap示例

// 创建TreeMap（按键自然排序）
Map<String, Integer> treeMap = new TreeMap<>();treeMap.put("Orange", 5);
treeMap.put("Apple", 10);
treeMap.put("Banana", 8);// 按键排序输出
treeMap.forEach((k, v) -> System.out.println(k)); // Apple, Banana, Orange// 定制排序
Map<String, Integer> reverseMap = new TreeMap<>(Comparator.reverseOrder());
reverseMap.putAll(treeMap);// 输出顺序：Orange, Banana, Apple// 导航方法
TreeMap<Integer, String> employeeMap = new TreeMap<>();
employeeMap.put(1001, "Alice");
employeeMap.put(1002, "Bob");
employeeMap.put(1003, "Charlie");Map.Entry<Integer, String> entry = employeeMap.floorEntry(1002); // 1002=Bob
Integer higherKey = employeeMap.higherKey(1001); // 1002// 范围视图
Map<Integer, String> subMap = employeeMap.subMap(1001, true, 1003, false); // 1001-1002

红黑树特性：

每个节点是红色或黑色
根节点是黑色
所有叶子节点(NIL)是黑色
红色节点的子节点必须是黑色
从任一节点到其每个叶子的路径包含相同数目的黑色节点

主要是TreeMap的底层结构就是红黑树，这里建议恶补一下数据结构的知识——红黑树、链表、二叉堆和二叉树等，方便理解。这里放两个链接：

二叉树和堆详解（通俗易懂）_堆和二叉树的区别-CSDN博客

【数据结构】红黑树超详解 ---一篇通关红黑树原理（含源码解析+动态构建红黑树）_红黑树的原理-CSDN博客

4.3 集合类选择

4.3.1 集合类选择指南

需要存储键值对时：
- 不需要排序：HashMap
- 需要保持插入/访问顺序：LinkedHashMap
- 需要按键排序：TreeMap
- 需要线程安全：ConcurrentHashMap
只需要存储元素时：
- 允许重复、需要索引：ArrayList/LinkedList
- 不允许重复、不关心顺序：HashSet
- 不允许重复、需要保持插入顺序：LinkedHashSet
- 不允许重复、需要排序：TreeSet
需要队列功能时：
- 普通队列：ArrayDeque
- 优先级队列：PriorityQueue
- 线程安全队列：LinkedBlockingQueue
需要线程安全时：
- List：CopyOnWriteArrayList
- Set：CopyOnWriteArraySet
- Map：ConcurrentHashMap
- Queue：LinkedBlockingQueue

4.3.2 集合类选择决策树

字有点小，建议点开了以后放大看！！

决策树文字说明：

第一层决策：存储类型
- 键值对 → 进入Map分支
- 单元素 → 进入Collection分支
Map分支选择逻辑：
- 需要排序？→ TreeMap(自然排序)或ConcurrentSkipListMap(线程安全排序)
- 不需要排序但需要顺序？→ LinkedHashMap(可配置插入顺序或访问顺序)
- 都不需要 → HashMap(最高性能)或ConcurrentHashMap(线程安全)
Collection分支选择逻辑：
- 允许重复(List/Queue)：
  - 需要索引 → ArrayList(随机访问快)或LinkedList(插入删除快)
  - 需要队列 → ArrayDeque(标准队列)或PriorityQueue(优先级队列)
  - 线程安全 → CopyOnWriteArrayList或BlockingQueue实现类
- 不允许重复(Set)：
  - 需要排序 → TreeSet或ConcurrentSkipListSet
  - 需要插入顺序 → LinkedHashSet
  - 只需要去重 → HashSet