跳到主要内容
约 10 分钟3 张卡

Java 集合框架

Java 集合框架是 java.util 里用来存放和组织一组对象的接口与实现。它分两层:接口规定元素怎样组织,比如能不能重复、有没有顺序、按什么规则取出;具体实现决定这些操作要花多少时间和内存。

所以选集合要分两步:先根据业务需要的行为选接口(List、Set、Map、Queue),再根据访问方式、数据规模和线程共享情况选实现。本文内容基于 Java 21 API。

1. 面试核心​

先记住这几条,再读正文
  • List、Set、Queue 都继承自 Collection,Map 不属于 Collection,是独立的一支。卡 · 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> 表示从键到值的映射,它不继承 Collection。下图省略了 Java 21 新增的有序接口:

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

Map

为什么 Map 单独一支?因为访问方式不同:Collection 操作的是一个个元素,Map 操作的是键值对,要通过键找到值,add(E) 这样的方法对它没有意义。不过 Map 可以通过 entrySet()、keySet() 和 values() 把条目、键和值以集合的形式交出来。这些都是视图,和原 Map 共享数据,通过视图删除元素(视图支持删除时),原 Map 里的对应条目也会被删掉。

Java 21 新增了 SequencedCollection,用来统一描述有确定遇到顺序的集合。遇到顺序就是遍历时依次看到元素的顺序,比如 List 的位置顺序。List 和 Deque 都继承了这个接口,可以用统一的方法访问两端元素,用 reversed() 得到反向视图。同时新增的 SequencedSet 和 SequencedMap 分别对应有遇到顺序的 Set 和 Map,比如 LinkedHashSet 和 LinkedHashMap。

3. List​

List 是有顺序、允许重复的序列,每个元素都有一个下标位置。下面这些需求适合用 List:

  • 需要按索引访问。
  • 需要保留插入或业务排序后的顺序。
  • 同一个值可以出现多次。
  • 需要在特定位置插入或替换。
List<String> steps = new ArrayList<>();
steps.add("validate");
steps.add("persist");
steps.add("publish");

String second = steps.get(1);

steps 按添加顺序保存三个步骤,下标从 0 开始,所以 get(1) 取到的是 "persist"。如果再 add("validate"),同一个步骤会出现在两个位置上,List 不会去重。

一般的顺序列表用 ArrayList:随机访问 O(1),尾部追加摊销 O(1),引用连续存放,顺序遍历对缓存也友好。

LinkedList 同时实现了 List 和 Deque,但按下标访问要一个个节点走过去。只有已经用迭代器停在某个位置、要在那里频繁增删时,它才能直接改节点链接、省掉定位的成本。只需要单线程队列时,优先考虑 ArrayDeque。

4. Set​

Set 用来去重和判断元素是否存在。它按自己的相等规则判断两个元素是否重复,已经存在的元素再添加一次,集合不会变化:

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

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

同一个权限字符串添加了两次,size 仍是 1;第二次 add 返回 false,表示没有加入。不同的实现在遍历顺序和查询能力上差别很大:

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

HashSet 内部其实是一个 HashMap,元素作为它的键存放。所以用自定义类型做元素时,equals 相等的对象必须返回相同的 hashCode,否则两个相等的对象可能被分到不同的位置,去重和查找都会失败。具体机制见 HashMap。

5. Map​

Map 把键和值关联起来,适合通过一个稳定的键查找、更新或删除值:

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

User found = usersById.get(userId);

usersById 以用户 ID 为键,读取时直接用 userId 就能找到对应的用户,不用遍历。常见实现在键顺序和查询能力上的区别如下:

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

一个键只对应一个值,对同一个键再次 put 会覆盖原来的值。如果一个业务键要对应多条记录,比如一个部门有多名用户,可以把值定义成集合,或者重新设计一个能区分每条记录的键。下面把同一部门的用户放进同一个 List:

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

computeIfAbsent 在这个部门还没有列表时新建一个并放进 Map,然后返回这个部门的列表,再把用户加进去。每个部门键仍然只对应一个值,只是这个值是一个能装多名用户的列表。

6. Queue 与 Deque​

Queue 规定的是元素的取出规则。最常见的是先进先出(FIFO),也有 PriorityQueue 这样按优先级取出的。下面用 ArrayDeque 按 FIFO 处理任务:

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

offer 把任务放到队尾,poll 取出并移除队首任务,队列为空时返回 null。队满或队空导致操作失败时,Queue 提供两组方法,区别在于怎样报告失败:

操作失败时抛异常失败时返回特殊值
插入addoffer
读取队首elementpeek
取出队首removepoll

队列有容量限制,或者队空、队满本来就是正常情况时,用 offer、peek、poll 检查返回值,比捕获异常更自然。

Deque(双端队列)两端都能插入和取出,既可以当队列用,也可以当栈用:

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

push 把元素放到栈顶,pop 取出栈顶,顺序是后进先出。单线程下需要栈或双端队列时,优先用 ArrayDeque;旧的 Stack 类继承自 Vector,栈操作依靠自身或底层方法的同步保护,单线程使用通常不需要这份同步。多个调用组合成「检查非空、再出栈」时,仍要另外保证整个操作的原子性。

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

6.1 PriorityQueue​

PriorityQueue 的队首永远是比较顺序中最小的元素,不管元素是按什么顺序放进去的:

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

这里按截止时间比较任务,所以 peek 看到的是最早到期的任务,poll 把它取出来。但直接遍历 tasks 得到的顺序并不是按截止时间排好的,原因见第 8 节。需要完整的有序结果时,要逐个 poll,或者把元素复制出来排序。

7. 选型步骤​

选集合时,可以依次确认下面六个方面,先用前三条确定接口,再用后三条比较实现:

  1. 重复与覆盖:元素需要去重时考虑 Set,需要按键覆盖旧值时考虑 Map。
  2. 顺序要求:确认需要保留插入或访问的次序,还是按比较器排序、按队列规则取出。
  3. 主要访问方式:确定最频繁的操作是索引访问、成员判断、范围查询、两端操作还是优先级取出。
  4. 数据规模:估算元素数量。数据量大时,链表和树的节点对象、基本类型的装箱、哈希表的空桶和扩容都会明显占内存。
  5. 线程共享:多个线程读写同一个集合时,需要并发容器或外部同步。
  6. 可变性:调用方只需读取固定结果时,优先返回不可修改的快照。
需求常见起点
保持顺序并按索引读取ArrayList
去重,不要求顺序HashSet
去重并保留输入顺序LinkedHashSet
按键快速查找HashMap
按键范围查询TreeMap
单线程 FIFO 或双端操作ArrayDeque
取出当前最小或最大元素PriorityQueue
有界跨线程生产消费ArrayBlockingQueue

这张表只是起点。实际场景常常同时需要几种访问方式,一个集合满足不了,就组合使用。比如排行榜既要按分数排序,又要快速找到某个用户:可以用 TreeSet 排序,同时用一个 Map 按用户 ID 定位;也可以单独维护一个排名索引。选哪种取决于更新有多频繁,以及更常查的是某个人的排名还是一段名次范围。

核心阅读到这里

检查能否解释

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

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

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

PriorityQueue 内部是一个二叉堆:用数组存储的一棵完全二叉树,只要求每个父节点不大于它的子节点。这条约束保证了最小元素一定在堆顶(数组的第一个位置),但兄弟节点之间、不同分支之间的大小关系都没有规定。

成本也由这个结构决定。peek 直接读堆顶,是 O(1)。offer 和 poll 要沿着树的高度把元素调整到合适的位置,是 O(log n)。按对象调用 contains、remove(Object) 时,堆帮不上忙,只能线性查找,是 O(n)。

迭代器按内部数组的顺序遍历,而数组只满足父子约束、并没有整体排序,所以遍历结果不是有序的。比如依次放入 3、1、2,内部数组可能是 [1,3,2]。需要按比较顺序输出时,要连续调用 poll:每次取出最小项后,堆会重新调整,让下一个最小项来到堆顶。这样会把队列清空,要保留原数据就先复制一份。另外,优先级相同的元素按什么顺序取出没有规定。

9. 常见问题​

9.1 HashSet 每次遍历顺序都一样,能依赖它吗?​

不能。HashSet 按哈希桶组织元素,元素的位置取决于哈希值、当前容量和哈希冲突,扩容后遍历顺序还会变。某次运行顺序看起来稳定,只是那一次的数据恰好这样分布。需要插入顺序时用 LinkedHashSet,需要排序时用 TreeSet。

9.2 ArrayDeque 为什么不能放 null?​

9.3 集合变量声明成 final,集合就不能改了吗?​

9.4 Collection 和 Collections 有什么区别?​

10. 面试题卡片​

11. 参考资料​

来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明