Java 集合模块学习记录#
本文档记录 Java 集合框架(Collections Framework)的核心知识点、底层原理与常用示例代码。 适合作为学习笔记、复习资料与面试准备。
一、集合框架总览#
Java 集合框架提供了一套用于存储和操作一组对象的工具类,位于 java.util 包中。
1.1 整体结构#
Collection(接口)
├── List(有序、可重复、有索引)
│ ├── ArrayList
│ ├── LinkedList
│ └── Vector(线程安全)
├── Set(无序、不可重复)
│ ├── HashSet
│ ├── LinkedHashSet(有序)
│ └── TreeSet(可排序)
└── Queue(队列)
├── LinkedList
├── PriorityQueue
└── Deque → ArrayDeque
Map(接口,键值对,不属于 Collection)
├── HashMap
├── LinkedHashMap(有序)
├── TreeMap(可排序)
├── Hashtable(线程安全,已过时)
└── ConcurrentHashMap(线程安全,推荐)
1.2 两大核心接口#
| 接口 | 特点 | 常用实现 |
|---|---|---|
Collection | 存储单个元素的集合 | List / Set / Queue |
Map | 存储键值对(key-value) | HashMap / TreeMap |
重点:
Map不属于Collection体系,它是独立的顶层接口。
二、List 体系#
List 的特点:有序、可重复、支持索引访问。
2.1 ArrayList#
底层结构: 动态数组(Object[] elementData)
特点:
- 随机访问快(
getO(1)) - 尾部插入快,中间/头部插入删除慢(需移动元素)
- 线程不安全
扩容机制:
- 默认初始容量 10(首次添加元素时才分配)
- 扩容为原来的 1.5 倍:
newCapacity = oldCapacity + (oldCapacity >> 1)
常用方法示例:
import java.util.ArrayList;
import java.util.List;
public class ArrayListDemo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("Java"); // 添加元素
list.add("Python");
list.add(1, "C++"); // 指定索引插入
System.out.println(list); // [Java, C++, Python]
System.out.println(list.get(0)); // Java
System.out.println(list.size()); // 3
System.out.println(list.contains("Java")); // true
list.set(0, "Go"); // 修改元素
list.remove("Python"); // 按值删除
list.remove(0); // 按索引删除
for (String s : list) { // 增强 for 遍历
System.out.println(s);
}
}
}
2.2 LinkedList#
底层结构: 双向链表(Node { prev, item, next })
特点:
- 随机访问慢(
getO(n),需遍历) - 头尾插入删除快(O(1))
- 实现了
Deque,可作为队列/双端队列使用 - 线程不安全
示例:
import java.util.LinkedList;
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.addFirst("Start"); // 头部添加
list.addLast("End"); // 尾部添加
System.out.println(list); // [Start, A, B, End]
System.out.println(list.getFirst()); // Start
System.out.println(list.getLast()); // End
list.removeFirst();
list.removeLast();
System.out.println(list); // [A, B]
}
}
2.3 ArrayList vs LinkedList#
| 对比项 | ArrayList | LinkedList |
|---|---|---|
| 底层结构 | 动态数组 | 双向链表 |
| 随机访问 | O(1) 快 | O(n) 慢 |
| 头尾插入删除 | 慢(需移动) | O(1) 快 |
| 中间插入删除 | 慢 | 慢(需先找到位置) |
| 内存占用 | 较少(连续内存) | 较多(每个节点存前后指针) |
| 适用场景 | 查询多 | 频繁增删 |
2.4 Vector#
- 底层也是数组,线程安全(方法加
synchronized) - 扩容为原来 2 倍
- 效率低,已被
Collections.synchronizedList()或CopyOnWriteArrayList替代
三、Set 体系#
Set 的特点:不可重复(元素唯一)。
3.1 HashSet#
底层结构: 基于 HashMap,元素作为 key 存储(value 是固定的 PRESENT 对象)。
特点:
- 无序(不保证插入顺序)
- 元素唯一
- 允许一个
null元素 - 依赖元素的
hashCode()和equals()保证唯一性
去重原理: 添加元素时,先计算 hashCode 定位桶,再比较 equals,两者都相同才视为重复。
示例:
import java.util.HashSet;
import java.util.Set;
public class HashSetDemo {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
set.add("Java");
set.add("Python");
set.add("Java"); // 重复,添加失败,返回 false
System.out.println(set); // [Java, Python]
System.out.println(set.size()); // 2
System.out.println(set.contains("Java")); // true
for (String s : set) {
System.out.println(s);
}
}
}
自定义对象去重示例:
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
public class Student {
private int id;
private String name;
public Student(int id, String name) {
this.id = id;
this.name = name;
}
// 必须重写 hashCode 和 equals 才能正确去重
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return id == student.id && Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(id, name);
}
public static void main(String[] args) {
Set<Student> set = new HashSet<>();
set.add(new Student(1, "张三"));
set.add(new Student(1, "张三")); // hashCode 和 equals 相同,视为重复
System.out.println(set.size()); // 1
}
}
3.2 LinkedHashSet#
- 继承
HashSet,底层使用LinkedHashMap - 保留插入顺序(维护了一条双向链表)
- 元素唯一,性能略低于
HashSet
import java.util.LinkedHashSet;
import java.util.Set;
Set<String> set = new LinkedHashSet<>();
set.add("B");
set.add("A");
set.add("C");
System.out.println(set); // [B, A, C] —— 保持插入顺序
3.3 TreeSet#
底层结构: 基于 TreeMap(红黑树)。
特点:
- 自动排序(自然顺序或自定义
Comparator) - 元素唯一
- 不允许
null(会抛NullPointerException) - 增删查时间复杂度 O(log n)
import java.util.Set;
import java.util.TreeSet;
public class TreeSetDemo {
public static void main(String[] args) {
Set<Integer> set = new TreeSet<>();
set.add(5);
set.add(1);
set.add(3);
System.out.println(set); // [1, 3, 5] —— 自动升序
// 自定义 Comparator:降序
Set<Integer> desc = new TreeSet<>((a, b) -> b - a);
desc.add(5);
desc.add(1);
desc.add(3);
System.out.println(desc); // [5, 3, 1]
}
}
3.4 三种 Set 对比#
| 对比项 | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| 底层结构 | HashMap | LinkedHashMap | TreeMap(红黑树) |
| 顺序 | 无序 | 插入顺序 | 排序顺序 |
| 性能 | 最快 | 略慢 | 较慢(O(log n)) |
| null 元素 | 允许 1 个 | 允许 1 个 | 不允许 |
四、Map 体系#
Map 存储 键值对,key 唯一,value 可重复。
4.1 HashMap(重点)#
底层结构(JDK 8+): 数组 + 链表 + 红黑树
核心机制:
- 通过 key 的
hashCode()扰动计算得到 hash 值 - 通过
(n - 1) & hash计算数组下标(n 为数组长度,容量为 2 的幂) - 哈希冲突时挂在链表上,链表长度 > 8 且数组容量 ≥ 64 时转为红黑树
- 默认容量 16,负载因子 0.75,扩容为原来的 2 倍
- 允许一个
nullkey 和多个nullvalue - 线程不安全
put 流程简化:
- 计算 key 的 hash
- 定位数组下标,桶为空则直接放入
- 桶不为空:遍历链表/红黑树,key 相同则覆盖 value,否则追加到链表尾部
- 判断是否需要树化、是否需要扩容
常用方法示例:
import java.util.HashMap;
import java.util.Map;
public class HashMapDemo {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("Java", 95); // 添加/覆盖
map.put("Python", 88);
map.put("C++", 90);
System.out.println(map.get("Java")); // 95
System.out.println(map.containsKey("Go")); // false
System.out.println(map.size()); // 3
map.put("Java", 100); // 覆盖旧值
System.out.println(map.get("Java")); // 100
map.remove("C++"); // 删除
// 遍历方式一:entrySet(推荐,效率高)
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + " = " + entry.getValue());
}
// 遍历方式二:keySet
for (String key : map.keySet()) {
System.out.println(key + " -> " + map.get(key));
}
// 遍历方式三:forEach(Java 8+)
map.forEach((k, v) -> System.out.println(k + " " + v));
}
}
常用实用方法:
Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.getOrDefault("b", 0); // 不存在时返回默认值 0
map.putIfAbsent("a", 100); // 已存在则不覆盖
map.computeIfAbsent("c", k -> 10); // 不存在才计算并放入
map.merge("a", 1, Integer::sum); // 合并值,a 变为 2
4.2 LinkedHashMap#
- 继承
HashMap,在节点上增加了before/after指针维护双向链表 - 保留插入顺序(或访问顺序)
- 可实现 LRU 缓存(构造参数
accessOrder = true)
import java.util.LinkedHashMap;
import java.util.Map;
// LRU 缓存示例:控制容量为 3
public class LRUCacheDemo {
public static void main(String[] args) {
Map<Integer, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
return size() > 3; // 超过 3 个就淘汰最久未访问的
}
};
lru.put(1, "A");
lru.put(2, "B");
lru.put(3, "C");
lru.get(1); // 访问 1,1 变为最近使用
lru.put(4, "D"); // 容量超限,淘汰最久未访问的 2
System.out.println(lru); // {3=C, 1=A, 4=D}
}
}
4.3 TreeMap#
- 基于 红黑树,key 自动排序
- key 不能为
null - 增删查 O(log n)
- 可实现范围查找(
headMap、tailMap、subMap)
import java.util.Map;
import java.util.TreeMap;
Map<Integer, String> map = new TreeMap<>();
map.put(30, "C");
map.put(10, "A");
map.put(20, "B");
System.out.println(map); // {10=A, 20=B, 30=C}
System.out.println(map.firstKey()); // 10
System.out.println(map.headMap(25)); // {10=A, 20=B}
4.4 Hashtable 与 ConcurrentHashMap#
| 对比项 | HashMap | Hashtable | ConcurrentHashMap |
|---|---|---|---|
| 线程安全 | 否 | 是(全表锁) | 是(分段/CAS + synchronized) |
| 性能 | 最高 | 低 | 高 |
| null 键值 | 允许 | 不允许 | 不允许 |
| 推荐度 | 单线程首选 | 已过时 | 多线程首选 |
import java.util.concurrent.ConcurrentHashMap;
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("count", 1);
map.computeIfAbsent("a", k -> 0);
map.merge("count", 1, Integer::sum); // 线程安全的累加
五、迭代器与遍历#
5.1 Iterator#
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class IteratorDemo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String s = it.next();
if ("B".equals(s)) {
it.remove(); // 推荐用迭代器的 remove 删除元素
}
}
System.out.println(list); // [A, C]
}
}
5.2 重要陷阱:ConcurrentModificationException#
错误写法: 用增强 for 循环遍历时直接调用集合的 remove()
// ❌ 错误:会抛 ConcurrentModificationException
for (String s : list) {
if ("B".equals(s)) {
list.remove(s);
}
}
原因: 增强 for 底层是迭代器,集合的 remove() 会修改 modCount,而迭代器检查时发现 modCount != expectedModCount,抛出异常。
正确写法:
// ✅ 方式一:使用 Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
if ("B".equals(it.next())) {
it.remove();
}
}
// ✅ 方式二:Java 8+ 的 removeIf
list.removeIf("B"::equals);
六、Collections 工具类#
Collections 是操作集合的工具类(注意与 Collection 接口区分)。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class CollectionsDemo {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
Collections.addAll(list, 3, 1, 2); // 批量添加
Collections.sort(list); // 排序:[1, 2, 3]
Collections.reverse(list); // 反转:[3, 2, 1]
Collections.shuffle(list); // 随机打乱
System.out.println(Collections.max(list)); // 最大值
System.out.println(Collections.min(list)); // 最小值
// 线程安全包装
List<Integer> syncList = Collections.synchronizedList(new ArrayList<>());
// 不可变集合
List<Integer> immutable = Collections.unmodifiableList(list);
}
}
七、泛型在集合中的应用#
泛型让集合在编译期就能检查类型安全,避免强制类型转换。
import java.util.ArrayList;
import java.util.List;
// 泛型集合:只能存 String
List<String> names = new ArrayList<>();
names.add("张三");
// names.add(123); // ❌ 编译报错,类型不安全
// 通配符
// List<?> 任意类型
// List<? extends T> 上界,只能读
// List<? super T> 下界,只能写
public static void printAll(List<? extends Number> list) {
for (Number n : list) {
System.out.println(n);
}
}
八、集合选择建议#
| 需求 | 推荐集合 | 理由 |
|---|---|---|
| 大量随机访问 | ArrayList | get 为 O(1) |
| 频繁头尾增删 | LinkedList | 链表 O(1) |
| 元素去重、无需顺序 | HashSet | 去重最快 |
| 去重且保持插入顺序 | LinkedHashSet | 有顺序 |
| 去重且自动排序 | TreeSet | 红黑树排序 |
| 键值对、单线程 | HashMap | 性能最好 |
| 键值对、保持顺序 | LinkedHashMap | 插入顺序 |
| 键值对、按 key 排序 | TreeMap | 红黑树排序 |
| 键值对、多线程 | ConcurrentHashMap | 线程安全且高效 |
| 队列/栈 | ArrayDeque | 比 Stack/LinkedList 更优 |
九、常见面试题 & 易错点#
9.1 为什么 HashMap 的容量是 2 的幂?#
- 因为计算下标使用
(n - 1) & hash,当 n 为 2 的幂时,n - 1的二进制全是 1,能让 hash 的低位全部参与运算,减少哈希冲突,使分布更均匀。
9.2 HashMap 为什么线程不安全?#
- 多线程同时
put可能造成数据覆盖(JDK 8 前还有死循环问题)。 - 多线程场景应使用
ConcurrentHashMap。
9.3 重写 equals 为什么必须重写 hashCode?#
- 约定:
equals相等的两个对象,hashCode必须相同。 - 若只重写
equals,对象放入HashSet或作为HashMap的 key 时,可能因 hash 不同而无法正确去重/查找。
9.4 数组和集合的区别?#
| 对比项 | 数组 | 集合 |
|---|---|---|
| 长度 | 固定 | 可变 |
| 存储类型 | 基本类型 + 引用类型 | 只能存对象(引用类型) |
| 功能 | 简单 | 丰富(增删改查、排序等) |
9.5 List 去重有哪几种方式?#
import java.util.*;
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 2, 3, 3, 3));
// 方式一:利用 Set 去重
Set<Integer> set = new LinkedHashSet<>(list);
List<Integer> result1 = new ArrayList<>(set);
// 方式二:Stream 去重
List<Integer> result2 = list.stream().distinct().collect(java.util.stream.Collectors.toList());
// 方式三:contains 判断(效率低)
List<Integer> result3 = new ArrayList<>();
for (Integer i : list) {
if (!result3.contains(i)) {
result3.add(i);
}
}
9.6 ArrayList 遍历删除的正确姿势?#
见 5.2 节,推荐使用 Iterator.remove() 或 removeIf()。
十、知识总结#
- 集合分类:
Collection(List / Set / Queue)与Map两大体系。 - List 有序可重复:
ArrayList查快、LinkedList增删快。 - Set 不可重复:
HashSet无序、LinkedHashSet有序、TreeSet排序。 - Map 键值对:
HashMap是核心,JDK 8 后为"数组+链表+红黑树"。 - 线程安全: 优先
ConcurrentHashMap,而非Hashtable。 - 遍历删除: 使用
Iterator.remove()或removeIf(),避免ConcurrentModificationException。 - 选择原则: 根据"是否去重、是否需要顺序、读写场景、是否线程安全"综合选择。
学习建议:多用
Debug查看ArrayList扩容和HashMap桶结构,结合源码理解原理,效果更佳。