Java 集合框架:接口体系、常用实现、底层结构与线程安全
系统介绍了 Java 集合框架,涵盖时间空间复杂度分析、Collection 与 Map 体系结构、List Set Map 核心区别及常用实现类。详细对比了 ArrayList、LinkedList、HashMap、TreeMap 等底层结构与性能特点,提供选型速查表,并重点讲解了线程安全机制及并发容器使用建议,帮助开发者根据场景选择合适的集合类型。

系统介绍了 Java 集合框架,涵盖时间空间复杂度分析、Collection 与 Map 体系结构、List Set Map 核心区别及常用实现类。详细对比了 ArrayList、LinkedList、HashMap、TreeMap 等底层结构与性能特点,提供选型速查表,并重点讲解了线程安全机制及并发容器使用建议,帮助开发者根据场景选择合适的集合类型。

| 时间复杂度 | 增长趋势(n 变大时) | 快慢等级 | 典型例子(直觉记忆) |
|---|---|---|---|
| O(1) | 不变 | ⭐⭐⭐⭐⭐ 最快 | 数组/ArrayList get(i);HashSet/HashMap 平均 contains/get |
| O(log n) | 增长很慢 | ⭐⭐⭐⭐ 很快 | 二分查找;TreeSet/TreeMap(红黑树)查找/增删 |
| O(n) | 成比例增长 | ⭐⭐⭐ 中等 | 遍历;ArrayList contains;LinkedList get(i) |
| O(n log n) | 比 n 慢一截 | ⭐⭐ 偏慢(但常用) | 排序(归并/快排平均);很多'排序 + 遍历' |
| O(n²) | 急剧增长 | ⭐ 慢 | 双重循环暴力比较(两两对比) |
| O(2^n) | 爆炸增长 | ❌ 很慢 | 子集枚举、暴力选或不选 |
| O(n!) | 更爆炸 | ❌❌ 最慢 | 全排列暴力(旅行商暴力) |
记忆口诀:1、log、n、nlogn、n²、2^n、n!(越往后越慢)
| 空间复杂度 | 额外内存随 n 增长? | 省/费等级 | 典型例子(直觉记忆) |
|---|---|---|---|
| O(1) | 不增长 | ⭐⭐⭐⭐⭐ 最省 | 双指针、原地交换、只用几个变量 |
| O(log n) | 增长很慢 | ⭐⭐⭐⭐ 很省 | 递归栈(如二分、快排平均栈深) |
| O(n) | 线性增长 | ⭐⭐⭐ 常见 | HashSet/HashMap;辅助数组;队列/栈存 n 个元素 |
| O(n²) | 平方增长 | ⭐⭐ 很费 | 二维 DP 表 dp[n][n];邻接矩阵 |
| 更高 | 更快增长 | ⭐ 最费 | 三维 DP 等 |
记忆口诀:1、log、n、n²(越往后越费内存)
集合框架可以理解为:JDK 提供的一套'标准化的数据容器体系',用于存放和操作数据,让我们把精力放在业务逻辑上,而不是重复造轮子。
一个完整的集合框架通常包含三部分:
List/Set/Map),让我们在代码里'面向接口编程',不关心具体实现。ArrayList/HashMap),内部使用不同数据结构以达到不同性能特点。Collections、Arrays 等工具类。Java 容器主要分两大类:
Collection:单列集合(存一个个元素)Collection<E>
List<E>:有序、可重复Set<E>:唯一(去重)Queue<E> / Deque<E>:队列/双端队列(工程中也很常用)Map:键值对集合(key -> value)Map<K,V>不继承 CollectionMap 自成体系。List、Map、Set(其次是 Queue/Deque)。List<E>:List 是接口,E 是泛型元素类型;ArrayList 是 List 的实现类。ArrayList + HashMap + HashSet;要顺序:LinkedHash*;要排序/范围:Tree*;并发共享:ConcurrentHashMap;栈/队列:ArrayDeque。List<E>:最常用的集合接口之一,有序、可重复,绝大多数'结果集/展示列表/批量处理'都是 List。Collection<E> / Iterable<E>:很多方法参数会写成它们以提高通用性,但你写业务代码时还是以 List 为主。Set<E>:核心就是去重(元素唯一),常用于'判重/过滤重复/黑白名单/去重统计'等。SortedSet<E> / NavigableSet<E>:需要排序 + 范围查找时会用(比如按时间/ID 有序、取区间、取最近值),但比 Set 少很多。Map<K,V>:几乎所有项目都会大量用到,键值映射/快速查找/配置参数/聚合统计/分组结果等都离不开它。ConcurrentMap<K,V>:并发场景(缓存、计数器、共享状态)常用,尤其在多线程/高并发服务里。SortedMap<K,V> / NavigableMap<K,V>:需要按 key 有序 + 范围操作时用(如时间线、区间查询),频率低于 Map。List<E> 是什么?和 ArrayList 有什么关系?List 是'规则/标准'(接口)ArrayList 是'按这个规则做出来的具体东西'(实现类)E 是'里面装什么类型的元素'(泛型)把 List 当成'插座标准',它规定了你必须支持哪些功能:
比如能 add()、能 get()、能 remove()……
ArrayList 就像'某个品牌按这个标准生产出来的插座'。
同样符合 List 标准的,还有别的品牌/型号,比如 LinkedList。
所以:
List:规定能力(接口)ArrayList:具体实现(实现类)E 到底是什么?E 是泛型参数,意思是 Element(元素)。
举例:
List<String>:只能装字符串List<Integer>:只能装整数(实际上装的是 Integer,基本类型会装箱)List<User>:只能装 User 对象ArrayList实现了List:
ArrayList<E> implements List<E>
这句的意思就是:
ArrayList 具备 List 规定的一切功能。
List = new ArrayList()?你经常看到这种写法:
List<String> list = new ArrayList<>();
这叫面向接口编程,好处是:
以后如果你发现 ArrayList 不合适,想换成别的实现,改动很小:
List<String> list = new LinkedList<>();
业务代码只认 List 的规则(add/get/remove),不关心底层用的是哪种实现。
List<E>是一个'列表接口',规定了列表必须有哪些操作;ArrayList是List的一个实现类;E表示列表里元素的类型。
nullHashSet/LinkedHashSet 通常允许一个 nullget(i) / set(i, x):O(1)add(e):均摊 O(1)contains(x) / add(x) / remove(x):平均 O(1)get(i))| 对比项 | List(列表) | Set(集合) |
|---|---|---|
| 是否允许重复 | ✅ 允许重复 | ❌ 不允许重复(自动去重) |
| 是否有序 | ✅ 有序(通常按插入/索引顺序) | 取决于实现:HashSet 无序;LinkedHashSet 插入有序;TreeSet 排序有序 |
| 是否有索引 | ✅ 有索引(可按 index 访问) | ❌ 没有索引(不能 get(i)) |
| '查找快'指的是什么 | ✅ 按索引 get(i) 快 | ✅ 按值 contains(x) 快(HashSet 平均 O(1)) |
| 典型使用场景 | 需要顺序、需要重复、需要按位置取值 | 需要去重、需要快速判断是否存在 |
说明:这里的'快/慢'默认 平均情况,
n是元素个数。
| 结构 | 底层结构 | get(i) | set(i,x) | add(尾部) | add(中间) | remove(中间) | contains(x) | 是否有序 | 空间特点 |
|---|---|---|---|---|---|---|---|---|---|
| ArrayList | 动态数组 | O(1) | O(1) | 均摊 O(1)(扩容 O(n)) | O(n)(搬移) | O(n)(搬移) | O(n)(遍历) | ✅ | 较省,但会预留容量 |
| LinkedList | 双向链表 | O(n) | O(n) | O(1)(尾插) | O(1)* | O(1)* | O(n) | ✅ | 指针多,空间更大(cache 不友好) |
| HashSet | 哈希表 | — | — | 平均 O(1) | — | 平均 O(1) | 平均 O(1) | ❌(无序) | 用空间换时间,内存更大 |
| LinkedHashSet | 哈希表 + 链表 | — | — | 平均 O(1) | — | 平均 O(1) | 平均 O(1) | ✅(插入有序) | 比 HashSet 更占内存 |
| TreeSet | 红黑树 | — | — | O(log n) | — | O(log n) | O(log n) | ✅(排序有序) | 节点开销较大 |
key -> value 映射key 必须唯一,value 可重复HashMap 允许 1 个 null key;ConcurrentHashMap/Hashtable 不允许 null| 对比项 | HashMap | LinkedHashMap | TreeMap | ConcurrentHashMap |
|---|---|---|---|---|
| 核心特点 | 最快的通用键值查找 | 在 HashMap 上保持顺序 | 按 key 排序 | 线程安全高并发 |
| 顺序 | ❌ 无序 | ✅ 插入有序(或访问有序 LRU) | ✅ 排序有序 | ❌ 不保证全局顺序 |
| 查找/增删(平均) | O(1) | O(1) | O(log n) | O(1)(并发下更稳) |
| 是否允许 null key/value | ✅ 允许(1 个 null key) | ✅ 允许 | ❌ 不允许 null key | ❌ 不允许 null |
| 典型场景 | 统计/缓存索引/一般映射 | 需要'按插入顺序遍历'/LRU | 需要排序、范围查询 | 多线程共享 Map |
说明:
n是键值对数量;Hash* 的 O(1) 是平均情况。
| 结构 | 底层结构 | get(key) | put(key,val) | remove(key) | containsKey | 是否有序 | 特点 / 典型用途 |
|---|---|---|---|---|---|---|---|
| HashMap | 哈希表 | 平均 O(1) | 平均 O(1) | 平均 O(1) | 平均 O(1) | ❌ | 通用最快;遍历顺序不确定 |
| LinkedHashMap | 哈希表 + 双向链表 | 平均 O(1) | 平均 O(1) | 平均 O(1) | 平均 O(1) | ✅ 插入/访问有序 | 可做 LRU(accessOrder=true) |
| TreeMap | 红黑树 | O(log n) | O(log n) | O(log n) | O(log n) | ✅ key 排序 | 范围查询:subMap/headMap/tailMap |
| ConcurrentHashMap | 分段/桶级并发哈希(JDK8 后更细粒度) | 平均 O(1) | 平均 O(1) | 平均 O(1) | 平均 O(1) | ❌ | 高并发读写;不允许 null |
ArrayList(最常用)LinkedList(更多时候当 Deque 用)Vector/Stack(老类,通常不推荐新项目使用)HashSetLinkedHashSet(保持插入顺序)TreeSet(有序、支持范围查询)HashMap(最常用)LinkedHashMap(保持顺序 / 可实现 LRU)TreeMap(按 key 排序 / 范围查询)ConcurrentHashMap(并发场景)这张表就是'你该用哪个集合'的速查表。
| 典型场景 | 推荐实现类 | 接口 | 底层数据结构 | 典型复杂度 | 线程安全 | 备注 |
|---|---|---|---|---|---|---|
| 普通列表/结果集,随机访问多 | ArrayList | List | 动态数组 Object[] | get O(1),尾插均摊 O(1),中间改 O(n) | 否 | 最常用 List |
| 头尾频繁增删(队列/栈) | ArrayDeque | Deque | 循环数组 | 头尾操作均摊 O(1) | 否 | 推荐替代 Stack;不允许 null |
| 按优先级取最小/最大 | PriorityQueue | Queue | 堆 | offer/poll O(log n),peek O(1) | 否 | 不保证遍历有序 |
| 判重/去重 | HashSet | Set | 基于 HashMap | 平均 O(1) | 否 | 依赖 hashCode/equals |
| 去重 + 保持插入顺序 | LinkedHashSet | Set | LinkedHashMap(Hash + 双向链表) | 平均 O(1) | 否 | 遍历顺序=插入顺序 |
| 排序/范围查询(<=、区间) | TreeSet | NavigableSet | 红黑树(TreeMap) | O(log n) | 否 | 通常不接受 null(取决于比较器) |
| key 查 value / 分组统计 / 缓存 | HashMap | Map | 数组 + 链表/红黑树(JDK8+) | 平均 O(1) | 否 | 允许 1 个 null key |
| Map 保持插入顺序 / LRU | LinkedHashMap | Map | HashMap + 双向链表 | 平均 O(1) | 否 | 可实现 LRU |
| key 有序 + 范围查询 | TreeMap | NavigableMap | 红黑树 | O(log n) | 否 | 适合区间/最值 |
| 多线程共享 Map | ConcurrentHashMap | ConcurrentMap | 并发哈希结构 | 并发下接近 O(1) | 是 | 不允许 ;用原子 API |
先给结论:接口不保证线程安全,看实现类 + 使用方式。
ArrayList、HashMap、HashSet、LinkedHashMap、TreeMap …如果它们只是方法内局部变量(每次请求新建、不共享),一般没问题。
ConcurrentHashMap(最常用并发 Map)CopyOnWriteArrayList/Set(读多写少)Collections.synchronizedMap/List/Set(...)(同步包装)Vector/Hashtable/Stack(老的同步类,新项目一般不推荐)错误写法(复合操作有竞态):
if (!map.containsKey(k)) { map.put(k, v); }
正确写法(原子操作):
map.putIfAbsent(k, v); // 或 map.computeIfAbsent(k, kk -> createValue());
int[])和引用类型(String[])List<Integer>)List、Map、SetArrayList、HashMap、HashSetLinkedHashMap/LinkedHashSet;要排序/范围:TreeMap/TreeSetConcurrentHashMap,并用 computeIfAbsent/putIfAbsent 这类原子方法
微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具,Keycode 信息在线工具,online
JavaScript 字符串转义/反转义;Java 风格 \uXXXX(Native2Ascii)编码与解码。 在线工具,Escape 与 Native 编解码在线工具,online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具,JavaScript / HTML 格式化在线工具,online
Terser 压缩、变量名混淆,或 javascript-obfuscator 高强度混淆(体积会增大)。 在线工具,JavaScript 压缩与混淆在线工具,online
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
null| 读多写少并发 List/Set | CopyOnWriteArrayList/Set | List/Set | 写时复制数组 | 读 O(1),写 O(n) | 是 | 配置/白名单很适合 |
| 简单粗暴同步包装 | Collections.synchronizedXxx | 多种 | 外层锁包装 | 取决于内部实现 | 是 | 遍历仍需手动同步 |