Javajava算法
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 | 多种 | 外层锁包装 | 取决于内部实现 | 是 | 遍历仍需手动同步 |