Java集合框架总览
目录
二、List接口：ArrayList vs LinkedList
Java集合框架（Java Collections Framework）是Java编程中最基础、最常用的知识体系之一。无论是日常开发还是面试考察，集合框架都占据着举足轻重的地位。本文将从整体架构出发，深入剖析Collection与Map两大体系的核心设计思想。
一、集合框架的整体架构
Java集合框架主要由两大接口体系构成：Collection 和 Map。
1. Collection体系
Collection 是所有单列集合的根接口，它有三个重要子接口：
- List：有序、可重复的集合
- Set：不可重复的集合
- Queue：队列，用于处理排队场景
// List - 有序可重复
List<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
list.add("Java"); // 允许重复
// Set - 无序不可重复
Set<String> set = new HashSet<>();
set.add("Java");
set.add("Python");
set.add("Java"); // 不会添加成功
// Queue - 队列
Queue<String> queue = new LinkedList<>();
queue.offer("Java");
queue.offer("Python");
String first = queue.poll(); // "Java"
2. Map体系
Map 是键值对映射的根接口，每个key最多映射一个value。
// Map - 键值对
Map<String, Integer> map = new HashMap<>();
map.put("Java", 1);
map.put("Python", 2);
int value = map.get("Java"); // 1
Collection和Map的根本区别在于：Collection存储单个元素，Map存储键值对。这个设计思想贯穿了整个集合框架。
二、List接口：ArrayList vs LinkedList
List接口最常见的两个实现类是ArrayList和LinkedList，它们的底层数据结构截然不同，适用场景也完全不同。
1. ArrayList —— 基于动态数组
ArrayList底层使用Object[]数组实现，它是最常用的List实现类。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 存储元素的数组
transient Object[] elementData;
// 实际元素数量
private int size;
}
核心特性：
- 支持随机访问，通过下标访问元素的时间复杂度为O(1)
- 尾部添加元素的平均时间复杂度为O(1)
- 中间插入或删除元素需要移动后续元素，时间复杂度为O(n)
- 线程不安全
2. LinkedList —— 基于双向链表
LinkedList底层使用双向链表实现，同时实现了List和Deque接口。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
}
核心特性：
- 不支持随机访问，查找元素需要遍历，时间复杂度为O(n)
- 头部和尾部的增删操作时间复杂度为O(1)
- 中间插入或删除需要先定位到节点，时间复杂度为O(n)
- 额外内存开销较大（每个节点需要存储前后指针）
- 线程不安全
3. 选型建议
// 场景1：频繁随机访问，使用ArrayList
List<String> names = new ArrayList<>();
names.get(100); // O(1) 高效
// 场景2：频繁在头部增删，使用LinkedList
LinkedList<String> queue = new LinkedList<>();
queue.addFirst("first"); // O(1)
queue.removeFirst(); // O(1)
// 场景3：已知大致容量，预设容量避免频繁扩容
List<String> bigList = new ArrayList<>(10000);
实际开发中的经验法则： 绝大多数场景下，ArrayList都是更好的选择。现代CPU的缓存机制对连续内存（数组）更加友好，即使在中间插入删除场景中，ArrayList的实际性能也经常优于LinkedList。
三、ArrayList扩容机制（面试高频考点）
ArrayList的扩容机制是面试中非常高频的考点，必须深入理解。
扩容触发条件
当向ArrayList中添加元素时，如果当前数组容量不足，就会触发扩容。
// 添加元素的核心逻辑
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保容量足够
elementData[size++] = e;
return true;
}
扩容流程详解
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 新容量 = 旧容量 * 1.5（位运算比乘法效率更高）
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 拷贝原数组到新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
关键点：
- 扩容倍数是1.5倍（不是2倍），通过
oldCapacity + (oldCapacity >> 1)实现 - 底层使用
Arrays.copyOf()，本质是调用System.arraycopy()进行内存拷贝 - 如果使用无参构造函数创建
ArrayList，初始容量为0（JDK8优化），第一次add时扩容为10 - 扩容操作涉及数组拷贝，性能开销较大，因此建议在已知容量时使用有参构造函数
// 性能对比
// 不预设容量 - 可能多次扩容
List<Integer> list1 = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
list1.add(i); // 可能触发多次扩容
}
// 预设容量 - 零扩容
List<Integer> list2 = new ArrayList<>(100000);
for (int i = 0; i < 100000; i++) {
list2.add(i); // 不会触发扩容
}
四、迭代器模式（Iterator Pattern）
迭代器模式是集合框架的核心设计模式之一，它提供了一种统一的方式来遍历集合元素，而无需暴露集合的内部结构。
Iterator接口
public interface Iterator<E> {
boolean hasNext(); // 是否还有下一个元素
E next(); // 返回下一个元素
void remove(); // 删除当前元素（可选操作）
}
迭代器的使用
List<String> list = new ArrayList<>(Arrays.asList("Java", "Python", "Go"));
// 方式1：for-each（本质是语法糖，底层也是迭代器）
for (String item : list) {
System.out.println(item);
}
// 方式2：显式使用迭代器
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String item = it.next();
System.out.println(item);
}
for-each的实现原理
for-each语法糖在编译后会被转换为迭代器模式：
// 编译前
for (String item : list) {
System.out.println(item);
}
// 编译后（等价代码）
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String item = it.next();
System.out.println(item);
}
五、fail-fast机制
fail-fast（快速失败）是Java集合框架中一个非常重要的错误检测机制。
什么是fail-fast
当多个线程在遍历集合时对集合进行结构性修改（添加、删除元素），或者在单线程遍历过程中通过非迭代器方式修改集合，迭代器会立即抛出ConcurrentModificationException。
List<String> list = new ArrayList<>(Arrays.asList("Java", "Python", "Go"));
// 错误示范：在for-each中删除元素
try {
for (String item : list) {
if ("Python".equals(item)) {
list.remove(item); // 抛出ConcurrentModificationException
}
}
} catch (ConcurrentModificationException e) {
System.out.println("触发了fail-fast机制！");
}
fail-fast的实现原理
ArrayList内部维护一个modCount（修改计数器），每次对集合进行结构性修改时，modCount会自增。迭代器在创建时会记录当前的modCount值为expectedModCount，每次调用next()时都会检查这两个值是否相等。
private class Itr implements Iterator<E> {
int expectedModCount = modCount;
public E next() {
checkForComodification(); // 检查是否被修改
// ... 返回元素逻辑
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
正确的删除方式
// 方式1：使用迭代器的remove方法
Iterator<String> it = list.iterator();
while (it.hasNext()) {
if ("Python".equals(it.next())) {
it.remove(); // 正确：会同步更新expectedModCount
}
}
// 方式2：使用removeIf（JDK8+）
list.removeIf(item -> "Python".equals(item));
// 方式3：反向遍历时使用List的remove
for (int i = list.size() - 1; i >= 0; i--) {
if ("Python".equals(list.get(i))) {
list.remove(i);
}
}
六、其他常用集合简介
HashSet
基于HashMap实现，元素作为key存储，value统一使用一个PRESENT对象。
// HashSet源码
public class HashSet<E> extends AbstractSet<E> implements Set<E> {
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
}
ArrayDeque
基于循环数组实现的双端队列，性能优于Stack和LinkedList。
// 推荐用ArrayDeque替代Stack
Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
String top = stack.pop(); // "second"
七、总结
| 特性 | ArrayList | LinkedList |
|---|---|---|
| 底层结构 | 动态数组 | 双向链表 |
| 随机访问 | O(1) | O(n) |
| 头部增删 | O(n) | O(1) |
| 尾部增删 | O(1)均摊 | O(1) |
| 内存占用 | 紧凑 | 较大（指针开销） |
| 线程安全 | 否 | 否 |
集合框架是Java编程的基石，理解其设计思想和实现原理，不仅能帮助我们写出更高效的代码，更是面试中展现技术深度的关键所在。
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
14
0- 0
已为社区贡献2条内容
所有评论(0)