Java 集合框架
Java 集合框架是 java.util 里用来存放和组织一组对象的接口与实现。它分两层:接口规定元素怎样组织,比如能不能重复、有没有顺序、按什么规则取出;具体实现决定这些操作要花多少时间和内存。
所以选集合要分两步:先根据业务需要的行为选接口(List、Set、Map、Queue),再根据访问方式、数据规模和线程共享情况选实现。本文内容基于 Java 21 API。
1. 面试核心
先记住这几条,再读正文List、Set、Queue都继承自Collection,Map不属于Collection,是独立的一支。卡 · ListList按位置保存元素,Set按相等规则去重,Map按键关联值。卡 · ListHashSet内部用HashMap存元素,先用hashCode定位、再用equals判断是否重复。卡 · SetPriorityQueue每次取出比较顺序中最小的元素,但直接遍历它得到的结果并不有序。卡 · 优先队列的遍历与复杂度- 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 提供两组方法,区别在于怎样报告失败:
| 操作 | 失败时抛异常 | 失败时返回特殊值 |
|---|---|---|
| 插入 | 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 类继承自 Vector,栈操作依靠自身或底层方法的同步保护,单线程使用通常不需要这份同步。多个调用组合成「检查非空、再出栈」时,仍要另外保证整个操作的原子性。
跨线程交接任务时,如果还需要等待和限制积压,见 BlockingQueue。
6.1 PriorityQueue
PriorityQueue 的队首永远是比较顺序中最小的元素,不管元素是按什么顺序放进去的:
Queue<Task> tasks = new PriorityQueue<>(
Comparator.comparing(Task::deadline)
);
这里按截止时间比较任务,所以 peek 看到的是最早到期的任务,poll 把它取出来。但直接遍历 tasks 得到的顺序并不是按截止时间排好的,原因见第 8 节。需要完整的有序结果时,要逐个 poll,或者把元素复制出来排序。
7. 选型步骤
选集合时,可以依次确认下面六个方面,先用前三条确定接口,再用后三条比较实现:
- 重复与覆盖:元素需要去重时考虑
Set,需要按键覆盖旧值时考虑Map。 - 顺序要求:确认需要保留插入或访问的次序,还是按比较器排序、按队列规则取出。
- 主要访问方式:确定最频繁的操作是索引访问、成员判断、范围查询、两端操作还是优先级取出。
- 数据规模:估算元素数量。数据量大时,链表和树的节点对象、基本类型的装箱、哈希表的空桶和扩容都会明显占内存。
- 线程共享:多个线程读写同一个集合时,需要并发容器或外部同步。
- 可变性:调用方只需读取固定结果时,优先返回不可修改的快照。
| 需求 | 常见起点 |
|---|---|
| 保持顺序并按索引读取 | 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?
因为 poll、peek 用返回 null 表示队列为空。如果允许放入 null,调用方拿到 null 时就分不清是取到了一个 null 元素,还是队列空了。所以 ArrayDeque 直接拒绝 null,传入会抛出 NullPointerException。业务需要表示「缺失」时,应该用专门的元素类型表达,和「没有元素」区分开。
9.3 集合变量声明成 final,集合就不能改了吗?
不是。final 只固定了变量里的引用,让它不能再指向另一个集合;集合对象本身如果支持修改,照样可以 add、remove。
只读视图、不可修改的副本和元素本身不可变,是三个不同层次的保证,具体区别见 集合迭代器。
9.4 Collection 和 Collections 有什么区别?
Collection 是集合的根接口。Collections 是工具类,提供排序、查找、包装成同步或不可修改集合等静态方法。类似的还有 Arrays,它是数组的工具类。
10. 面试题卡片
11. 参考资料
- Java API:Collection
- Java API:List
- Java API:Set
- Java API:Map
- Java API:Queue
- Java API:Deque
- Java 21:PriorityQueue
- Java 21:SequencedCollection
- Java 21:HashSet
- OpenJDK 21:Stack 源码
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明