容器选型总对比

ℹ️定位说明

本篇是 02-Java容器的收官对比篇：把四大系列散落各篇的选型知识收拢成"一张总表 + 一张复杂度表 + 一套线程安全方案"。速查用本篇，深读回各系列（List / Set / Queue / Map）。

一、两大体系全景

graph LR
    subgraph Collection["Collection（单值）"]
        L["List<br/>有序可重复"]
        S["Set<br/>唯一"]
        Q["Queue/Deque<br/>队列/双端"]
    end
    M["Map（键值对）<br/>键唯一值可重复"]
    ROOT["Iterable"]
    ROOT --> Collection
    ROOT -.->|"独立体系（不是 Collection）"| M
    L --> AL["ArrayList（默认）"] & LL["LinkedList"] & V["Vector（遗留）"]
    S --> HS["HashSet（默认）"] & LHS["LinkedHashSet（保序）"] & TS["TreeSet（排序）"]
    Q --> PQ["PriorityQueue（堆）"]
    Q --> AD["ArrayDeque（双端/栈）"]
    M --> HM["HashMap（默认）"] & LHM["LinkedHashMap（LRU）"] & TM["TreeMap（排序）"]

一句话框架：Collection 家族"装单个元素"，Map 家族"装键值对"；Map 不是 Collection 的子接口，它是平行的另一棵树（但 values() 返回 Collection、keySet() 返回 Set，两者互通）。

二、常用实现一张总表

实现类	所属族	底层结构	顺序	去重/键判定	null 支持	平均复杂度	一句话定位
ArrayList	List	动态数组	插入序	可重复	✅	查 O(1) 改 O(n)	默认 List
LinkedList	List+Deque	双向链表	插入序	可重复	✅	头尾 O(1) 查 O(n)	头尾操作/当队列栈（但栈首选 ArrayDeque）
Vector	List	动态数组+方法锁	插入序	可重复	✅	查 O(1) 锁开销大	遗留，不用
HashSet	Set	哈希表（HashMap）	无序	hashCode+equals	1 个 null	O(1)	默认 Set
LinkedHashSet	Set	哈希表+双向链表	插入序	同 HashSet	1 个 null	O(1) 微开销	去重且保序
TreeSet	Set	红黑树（TreeMap）	排序	compareTo/compare==0	❌	O(log n)	排序+范围查询
ArrayDeque	Deque	循环数组	无序	—	❌	头尾均摊 O(1)	栈/双端首选
PriorityQueue	Queue	二叉最小堆	优先级出队	可重复	❌	O(log n)	Top K/调度
HashMap	Map	数组+链表+红黑树	无序	hashCode+equals	1 null 键	O(1)	默认 Map
LinkedHashMap	Map	哈希表+双向链表	插入/访问序	同 HashMap	1 null 键	O(1) 微开销	LRU 现成地基
TreeMap	Map	红黑树	键排序	compareTo==0	❌ null 键	O(log n)	排序映射+范围查询
Hashtable	Map	哈希表+方法锁	无序	同 HashMap	❌	O(1) 锁开销大	遗留，用 ConcurrentHashMap

三、复杂度速查

操作	ArrayList	LinkedList	HashSet/HashMap	TreeSet/TreeMap	ArrayDeque	PriorityQueue
随机访问	O(1)	O(n)	—	O(log n)	—	—
头部插/删	O(n)	O(1)	—	—	O(1)	—
尾部插/删	O(1) 均摊	O(1)	—	—	O(1)	O(log n) offer
按内容查找	O(n)	O(n)	O(1)	O(log n)	O(n)	O(n)
插入（中间）	O(n)	O(n)（定位 O(n) + 改指针 O(1)）	—	—	—	—
取最值	O(n)	O(n)	—	O(log n)（first/last 是 O(1)？核对点：TreeMap firstKey 走最左节点，O(log n)）	—	O(1) peek

四、线程安全方案对照

方案	原理	代价	适用
`Vector` / `Hashtable`	方法级 `synchronized`（遗留）	粗粒度锁，读读互斥	只剩旧代码兼容
`Collections.synchronizedXxx()`	包装器，同粗粒度锁	与 Vector 相当	任意容器快速加锁，语义清晰
`CopyOnWriteArrayList`	写时复制新数组	写贵（复制全量），读完全无锁	读多写极少（监听器列表、配置缓存）
`ConcurrentHashMap`	JDK 8：CAS + synchronized 锁单桶	细粒度，并发度高	并发 Map 唯一正解
`ConcurrentLinkedQueue`	无锁 CAS 链表	无阻塞	高并发无界队列
`BlockingQueue` 家族	锁 + 条件阻塞	阻塞语义	生产者-消费者（`ArrayBlockingQueue`/`LinkedBlockingQueue`）

记忆主线：遗留类（Vector/Hashtable/Stack）三兄弟全部淘汰；替代思路都是"把锁变小"——要么锁单个桶（ConcurrentHashMap），要么干脆不锁靠复制（CopyOnWriteArrayList），要么无锁 CAS。阻塞与并发细节等 03-Java并发分区展开。

五、选型三问（收束）

装什么形态？ 单值 → Collection 三族；键值对 → Map 三族。
要什么顺序？ 无所谓 → HashSet/HashMap（默认）；保插入序 → Linked 系；要排序/范围 → Tree 系。
什么环境？ 单线程 → 上面的默认答案；多线程 → 第四节并发方案，且细节留给并发分区。

高频翻车点都记在对应系列总览里：remove 重载歧义与 Arrays.asList 定长坑见 00-List总览，retainAll 就地修改见 00-Set总览，merge/getOrDefault 套路见 00-Map总览。

⬅️ 红黑树 🏠 00-Java ➡️ 01-容器高频面试题

00-容器选型总对比