约 9 分钟3 张卡

Java 集合框架

Java 集合框架用接口约定元素怎样组织，再由具体实现决定操作成本。本文先区分 Collection 与 Map，再比较列表、集合、映射和队列的用途。最后根据访问方式、内存和线程共享需求选择实现。内容采用 Java 21 API。

1. 面试核心

先记住这几条，再读正文

接口关系。 List、Set、Queue 属于 Collection 分支，Map 独立于该分支。卡 · List
数据组织。 List 按位置保存元素，Set 按相等规则去重，Map 按键关联值。卡 · List
哈希去重。 HashSet 基于 HashMap，通过 hashCode 与 equals 判断重复。卡 · Set
优先队列。 PriorityQueue 按比较顺序取出当前最小元素，普通遍历得到的结果没有整体排序。卡 · 优先队列的遍历与复杂度
有序集合接口。 Java 21 的 SequencedCollection 为具有确定遍历次序的集合统一提供两端访问和反向视图。

2. Collection 与 Map

Collection<E> 表示一组元素。常用分支包括 List、Set 和 Queue。Map<K, V> 表示键到值的映射，它是独立分支。

下图省略 Java 21 新增的有序接口：

Iterable
└── Collection
    ├── List
    ├── Set
    └── Queue
        └── Deque

Map

这个划分来自访问方式：Collection 按元素处理，Map 则通过键定位值。Map 可以通过 entrySet()、keySet() 和 values() 提供条目、键和值的集合视图。视图与原 Map 共享数据，所以通过支持删除的视图移除元素，也会修改原 Map。

Java 21 引入 SequencedCollection，统一描述有确定“遇到顺序”的集合。遇到顺序就是遍历时看到元素的次序，例如 List 的位置顺序。List 与 Deque 都继承该接口，支持两端访问及 reversed() 反向视图。SequencedSet 和 SequencedMap 则分别扩展有序集合与映射。

3. List

必会卡 · List、Set、Map 分别适合什么场景

List 是有顺序、允许重复的序列，每个元素都有位置。业务需要以下位置与顺序能力时，可以选择 List：

需要按索引访问。
需要保留插入或业务排序后的顺序。
同一个值可以出现多次。
需要在特定位置插入或替换。

List<String> steps = new ArrayList<>();
steps.add("validate");
steps.add("persist");
steps.add("publish");

String second = steps.get(1);

上例按添加顺序保存三个步骤，所以 get(1) 取得的是 "persist"。索引从 0 开始，允许重复意味着相同步骤也能出现在不同位置。

ArrayList 适合一般顺序列表：随机访问为 O(1)，尾部追加摊销 O(1)。它连续保存引用，顺序遍历也有较好的缓存局部性。

LinkedList 同时实现 List 和 Deque，但按索引访问需要逐个经过节点。已有迭代位置并频繁在该处增删时，才能直接修改节点链接，省去定位成本。单线程队列则可优先考虑 ArrayDeque。

4. Set

必会卡 · HashSet 怎样判断元素重复

Set 用来去重和判断元素是否存在。同一个集合按自己的相等规则判断重复，重复添加已有元素会保持元素数量不变：

Set<String> permissions = new HashSet<>();
permissions.add("order:read");
permissions.add("order:read");

System.out.println(permissions.size()); // 1

上例两次添加同一个权限字符串，最终 size 为 1。选择具体实现时，还要比较遍历顺序和查询能力：

实现	顺序	典型操作	适用情况
`HashSet`	不承诺遍历顺序	平均常数时间	只关心去重和成员判断
`LinkedHashSet`	保留遇到顺序	平均常数时间，额外维护链	去重后仍需稳定顺序
`TreeSet`	按自然顺序或 Comparator 排序	对数时间	范围查询、前驱后继、有序输出
`EnumSet`	枚举声明顺序	位向量实现	一组枚举标志

HashSet 把元素作为 HashMap 的键存放。自定义元素需要让相等对象返回相同哈希值，才能正确查找和去重。具体机制见 HashMap。

5. Map

Map 适合通过稳定键查找、更新或删除值：

Map<Long, User> usersById = new HashMap<>();
usersById.put(user.id(), user);

User found = usersById.get(userId);

上例用用户 ID 作为键，所以读取时可以直接按 userId 查找用户。常见实现的顺序与查询能力如下：

实现	键顺序	典型复杂度	主要用途
`HashMap`	不承诺	平均 O(1)	一般键值查找
`LinkedHashMap`	插入顺序或访问顺序	平均 O(1)	稳定遍历、简单 LRU
`TreeMap`	排序	O(log n)	范围、最近键、有序导航
`EnumMap`	枚举声明顺序	接近数组访问	枚举键
`ConcurrentHashMap`	不承诺	并发实现	多线程共享映射

Map 为一个键保存一个当前值，对同一个键再次 put 会替换原值。一个业务键需要对应多条记录时，可以把值定义成集合，或重新设计能区分记录的键。下面把同一部门的用户放入一个 List：

Map<Department, List<User>> usersByDepartment = new HashMap<>();
usersByDepartment
    .computeIfAbsent(user.department(), ignored -> new ArrayList<>())
    .add(user);

computeIfAbsent 在部门还没有对应列表时创建列表，之后把用户加入该列表。这样，每个部门键仍只对应一个值，但这个值可以保存多名用户。

6. Queue 与 Deque

Queue 约定元素的取出规则。FIFO 指先进先出，PriorityQueue 则按优先级取出。下面的 ArrayDeque 按 FIFO 处理任务：

Queue<Job> jobs = new ArrayDeque<>();
jobs.offer(job);
Job next = jobs.poll();

offer 把任务放到队尾，poll 取出并移除队首任务，队空时返回 null。处理队满或队空时，可以选择以下两组方法：

操作	失败时抛异常	失败时返回特殊值
插入	`add`	`offer`
读取队首	`element`	`peek`
取出队首	`remove`	`poll`

有容量限制或失败属于正常控制流时，offer、peek 和 poll 更容易处理。

Deque 支持两端操作，可以作为队列或栈：

Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
Node current = stack.pop();

上例的 push 把元素放到栈顶，pop 取出栈顶，形成后进先出的顺序。单线程栈和双端队列可优先使用 ArrayDeque，它也能替代旧的 Stack 类。

跨线程交接任务时，如果还需要等待和限制积压，见 BlockingQueue。

6.1 PriorityQueue

PriorityQueue 的队首是比较顺序中的最小元素：

Queue<Task> tasks = new PriorityQueue<>(
    Comparator.comparing(Task::deadline)
);

上例按截止时间比较任务，所以 peek 查看的是最早到期的任务，poll 则将它取出。普通遍历没有整体排序，需要完整有序结果时，应逐个 poll 或使用排序算法。

7. 选型步骤

必会卡 · List、Set、Map 分别适合什么场景

选择集合时，可以围绕数据组织与访问需求确认以下六个方面，再比较实现成本：

重复与覆盖：元素需要去重时考虑 Set，需要按键覆盖旧值时考虑 Map。
顺序要求：确认需要保留插入或访问的次序，还是按比较器排序、按队列规则取出。
主要访问方式：确定最频繁的操作是索引访问、成员判断、范围查询、两端操作还是优先级取出。
数据规模：估算元素数量，因为节点对象、装箱、空桶和扩容都占内存。
线程共享：多个线程读写同一个集合时，需要并发容器或外部同步。
可变性：调用方只需读取固定结果时，优先返回不可修改的快照。

需求	常见起点
保持顺序并按索引读取	`ArrayList`
去重，不要求顺序	`HashSet`
去重并保留输入顺序	`LinkedHashSet`
按键快速查找	`HashMap`
按键范围查询	`TreeMap`
单线程 FIFO 或双端操作	`ArrayDeque`
取出当前最小或最大元素	`PriorityQueue`
有界跨线程生产消费	`ArrayBlockingQueue`

一个场景可以组合多种访问方式。例如，排行榜可以用 TreeSet 排序，同时用 Map 定位用户；也可以单独维护排名索引。最终选择取决于更新频率，以及要查询个人排名还是一段排名范围。

核心阅读到这里

检查能否解释

根据顺序、去重、键值查找和取出规则选择容器，并说明依据。

List、Set、Map 分别适合什么场景？查看题目与参考回答 →

下一篇：ArrayList 返回主题目录查看其他复习主题

8. 优先队列的遍历与复杂度

必会卡 · PriorityQueue 的遍历结果有序吗，怎样获得有序结果？

PriorityQueue 的效率来自优先堆，也就是让最小元素保持在堆顶的结构。堆只维护父子节点之间的顺序约束，其余元素的位置由这个约束决定。Java 21 中，peek 直接读取堆顶，成本为 O(1)。offer 和 poll 要沿堆的高度调整元素，成本为 O(log n)。按对象调用 contains、remove 则需线性查找，成本为 O(n)。

迭代器按内部存储遍历，所以遍历结果没有整体排序。需要按比较顺序升序输出时，应连续 poll。每次取出最小项后，堆会重新维护队首。这会消费原队列，因此要保留原数据时先复制。相同优先级的元素可以按任意次序取出。