我要评论前言
1. 本文主要介绍 java 标准库中 java.util 包下的集合框架，不涉及 java.util.concurrent（juc）包中的并发集合类。
2. 文章侧重于常用集合类及其常用 api 的整理与总结，旨在为日常开发提供查阅参考，不涉及底层原理或面试相关问题的深入探讨。
集合框架概述
图 1：java 集合框架结构图（图源自 java guide）
java 中的集合（也称为容器）框架主要由两大核心接口组成：
- collection 接口：用于存储单个元素的集合，常见的子接口包括
list、set和queue； - map 接口：用于存储键值对形式的数据。
其中，collection 是最基础的集合接口，根据元素的组织方式又衍生出以下三种常用子接口：
list
- 元素有序、可重复，支持通过索引访问。
- 常见实现类：
arraylist、linkedlist、vector。
set
- 元素无序、不可重复，适用于去重场景。
- 常见实现类：
hashset、linkedhashset、treeset。 - 派生子接口：
sortedset（如treeset），用于提供有序集合支持。
queue
- 用于队列结构，强调元素的处理顺序。
- 常见实现类：
linkedlist、priorityqueue、arraydeque。 - 派生子接口：
deque（双端队列接口），支持从两端插入和删除元素。
而 map 接口则用于保存键值对（key-value）结构的数据：
- 常见实现类：
hashmap、linkedhashmap、treemap、hashtable。 - 派生子接口：
sortedmap（如treemap），用于维护键的有序性。
注：集合框架中的一些接口（如 sortedset、deque、sortedmap）并不常在项目中直接使用，但它们是一些重要实现类（如 treeset、arraydeque、treemap）的核心接口，理解这些结构有助于掌握集合的使用与底层行为。
list 接口常用 api
list 接口表示有序、可重复的元素集合，支持通过索引访问元素。
常见实现类有：
arraylist：基于动态数组实现，支持快速随机访问，但在数组中间插入或删除元素时性能较差。linkedlist：基于双向链表实现，在两端插入和删除元素较快，但随机访问元素需要从头或尾遍历，性能较低。
常用方法汇总
| 方法名 | 说明 | 返回值 | 时间复杂度 |
|---|---|---|---|
| add(e e) | 向列表尾部添加元素 | boolean | arraylist: o(1) 均摊；linkedlist: o(1) |
| add(int index, e e) | 在指定位置插入元素 | void | o(n) |
| get(int index) | 获取指定索引位置的元素 | e | arraylist: o(1)；linkedlist: o(n) |
| set(int index, e e) | 替换指定索引位置的元素 | e | arraylist: o(1)；linkedlist: o(n) |
| remove(int index) | 移除指定索引处的元素 | e | o(n) |
| remove(object o) | 移除首次出现的指定元素 | boolean | o(n) |
| contains(object o) | 判断是否包含指定元素 | boolean | o(n) |
| indexof(object o) | 返回首次出现的索引 | int | o(n) |
| lastindexof(object o) | 返回最后一次出现的索引 | int | o(n) |
| size() | 返回列表中的元素个数 | int | o(1) |
| isempty() | 判断列表是否为空 | boolean | o(1) |
| clear() | 清空所有元素 | void | o(n) |
| toarray() | 转为数组 | object[] | o(n) |
set 接口常用 api
set 接口表示不允许包含重复元素的集合，主要用于保证元素的唯一性。
常见实现类有：
hashset：基于哈希表实现，支持快速插入、删除和查找，元素无序。linkedhashset：继承自 hashset，使用链表维护元素插入顺序，迭代顺序稳定。treeset：基于红黑树实现，元素有序，支持排序操作。
常用方法汇总
| 方法名 | 说明 | 返回值 | 时间复杂度 |
|---|---|---|---|
| add(e e) | 添加元素 | boolean | o(1) 均摊 |
| remove(object o) | 移除指定元素 | boolean | o(1) 均摊 |
| contains(object o) | 判断是否包含指定元素 | boolean | o(1) 均摊 |
| size() | 返回集合中的元素个数 | int | o(1) |
| isempty() | 判断集合是否为空 | boolean | o(1) |
| clear() | 清空所有元素 | void | o(n) |
| iterator() | 返回迭代器 | iterator<e> | o(1) |
| toarray() | 转为数组 | object[] | o(n) |
注：treeset 也是 set 接口的实现类，时间复杂度的分析将在 sortedset 部分介绍。
queue 接口常用 api
queue 接口表示一个**先进先出（fifo）**的集合，常用于按队列方式管理元素。
常见实现类有：
linkedlist：基于双向链表实现，既可作为队列，也可作为栈或双端队列。arraydeque：基于可变数组实现的双端队列，性能优于linkedlist。priorityqueue：基于最小堆实现的优先级队列，元素按优先级出队（非 fifo）。
常用方法汇总
| 方法名 | 说明 | 返回值 | 时间复杂度 |
|---|---|---|---|
| add(e e) | 添加元素（失败抛异常） | boolean | o(1) |
| offer(e e) | 添加元素（失败返回 false） | boolean | o(1) |
| remove() | 移除并返回队头元素（队空抛异常） | e | o(1) |
| poll() | 移除并返回队头元素（队空返回 null） | e | o(1) |
| element() | 查看队头元素（队空抛异常） | e | o(1) |
| peek() | 查看队头元素（队空返回 null） | e | o(1) |
| isempty() | 判断队列是否为空 | boolean | o(1) |
| size() | 返回队列中元素个数 | int | o(1) |
| clear() | 清空队列所有元素 | void | o(n) |
注：priorityqueue 也实现了 queue 接口，但其底层为最小堆，相关操作如 add、offer、poll、peek 的时间复杂度均为 o(log n)。
map 接口常用 api
map 接口用于存储键值对（key-value），每个 key 对应一个 value，且 key 不允许重复。常用于查找、映射和数据缓存等场景。
常见实现类包括：
hashmap：基于哈希表实现，支持快速查找、插入、删除，key 无序。linkedhashmap：继承自 hashmap，使用链表维护插入顺序，迭代顺序稳定。
常用方法汇总
| 方法名 | 说明 | 返回值 | 时间复杂度 |
|---|---|---|---|
| put(k key, v value) | 添加或更新键值对 | v | o(1) 均摊 |
| get(object key) | 获取指定 key 对应的 value | v | o(1) 均摊 |
| remove(object key) | 移除指定 key 的映射关系 | v | o(1) 均摊 |
| containskey(object key) | 判断是否包含指定 key | boolean | o(1) 均摊 |
| containsvalue(object v) | 判断是否包含指定 value | boolean | o(n) |
| size() | 返回映射关系对数（键值对个数） | int | o(1) |
| isempty() | 判断是否为空 | boolean | o(1) |
| clear() | 清空所有键值对 | void | o(n) |
| keyset() | 返回所有 key 的集合 | set<k> | o(n) |
| values() | 返回所有 value 的集合 | collection<v> | o(n) |
| entryset() | 返回所有键值对的集合 | set<map.entry<k,v>> | o(n) |
注：treemap 也是 map 接口的实现类，但由于其基于红黑树，时间复杂度不同，详见 sortedmap 部分分析。
sortedset 接口常用 api
sortedset 接口是 set 的子接口，表示可排序的集合，其元素按照自然顺序或指定的比较器进行排序，常用于需要有序访问元素的场景。
常见实现类：
treeset：基于红黑树实现，元素自动排序，支持范围查询。
常用方法汇总
| 方法名 | 说明 | 返回值 | 时间复杂度 |
|---|---|---|---|
| add(e e) | 添加元素 | boolean | o(log n) |
| remove(object o) | 移除指定元素 | boolean | o(log n) |
| contains(object o) | 判断是否包含指定元素 | boolean | o(log n) |
| first() | 返回集合中第一个（最小）元素 | e | o(log n) |
| last() | 返回集合中最后一个（最大）元素 | e | o(log n) |
| headset(e toelement) | 返回严格小于指定元素的子集 | sortedset | o(log n) |
| tailset(e fromelement) | 返回大于等于指定元素的子集 | sortedset | o(log n) |
| subset(e from, e to) | 返回范围 [from, to) 的子集 | sortedset | o(log n) |
| size() | 返回元素个数 | int | o(1) |
| isempty() | 判断集合是否为空 | boolean | o(1) |
| clear() | 清空所有元素 | void | o(n) |
| iterator() | 返回按升序排列的迭代器 | iterator<e> | o(1) |
deque 接口常用 api
deque（double ended queue）接口表示双端队列，支持从队列两端插入和删除元素。它同时具备栈和队列的功能，是栈 (stack) 和队列 (queue) 的统一抽象。
常见实现类：
arraydeque：基于可变数组实现，性能优良，推荐优先使用。linkedlist：基于双向链表实现，功能丰富，但性能略逊。
常用方法汇总
| 方法名 | 说明 | 返回值 | 时间复杂度 |
|---|---|---|---|
| addfirst(e e) | 从队头添加元素 | void | o(1) |
| addlast(e e) | 从队尾添加元素 | void | o(1) |
| removefirst() | 移除并返回队头元素 | e | o(1) |
| removelast() | 移除并返回队尾元素 | e | o(1) |
| getfirst() | 获取但不移除队头元素 | e | o(1) |
| getlast() | 获取但不移除队尾元素 | e | o(1) |
| offerfirst(e e) | 从队头插入元素（推荐，带返回值） | boolean | o(1) |
| offerlast(e e) | 从队尾插入元素（推荐，带返回值） | boolean | o(1) |
| pollfirst() | 移除并返回队头元素（为空返回 null） | e | o(1) |
| polllast() | 移除并返回队尾元素（为空返回 null） | e | o(1) |
| peekfirst() | 获取但不移除队头元素（为空返回 null） | e | o(1) |
| peeklast() | 获取但不移除队尾元素（为空返回 null） | e | o(1) |
| isempty() | 判断是否为空 | boolean | o(1) |
| size() | 返回元素个数 | int | o(1) |
| clear() | 清空所有元素 | void | o(n) |
注：建议优先使用 offerxxx、pollxxx、peekxxx 这些方法，它们在队列为空或满时不会抛异常，更安全。
sortedmap 接口常用 api
sortedmap 接口继承自 map，表示按键排序的映射表，常见实现类为 treemap。
常用方法汇总
| 方法名 | 说明 | 返回值 | 时间复杂度 |
|---|---|---|---|
| comparator() | 返回用于排序的比较器，若为自然顺序则返回 null | comparator<? super k> | o(1) |
| firstkey() | 返回键的第一个（最低）元素 | k | o(log n) |
| lastkey() | 返回键的最后一个（最高）元素 | k | o(log n) |
| submap(k fromkey, k tokey) | 返回指定键范围的子映射 | sortedmap<k,v> | o(log n) |
| headmap(k tokey) | 返回小于 tokey 的键的子映射 | sortedmap<k,v> | o(log n) |
| tailmap(k fromkey) | 返回大于等于 fromkey 的键的子映射 | sortedmap<k,v> | o(log n) |
总结
以上为个人经验，希望能给大家一个参考，也希望大家多多支持代码网。
发表评论