Java-集合

一、集合框架整体架构

Java 集合框架位于 java.util 包，核心由 接口 + 实现类 + 工具类 构成。

核心接口关系图

Iterable
 └── Collection
      ├── List          → 有序、可重复（如 ArrayList, LinkedList）
      ├── Set           → 无序、不可重复（如 HashSet, TreeSet）
      └── Queue         → 队列（FIFO/LIFO，如 LinkedList, PriorityQueue）
            └── Deque   → 双端队列（如 ArrayDeque）

Map（不属于 Collection，但属于集合框架）
 ├── HashMap
 ├── TreeMap
 ├── LinkedHashMap
 └── ConcurrentHashMap

✅ 注意：Map 不是 Collection 的子接口，但它是集合框架的重要组成部分。

二、List 接口及实现类

实现类	底层数据结构	是否线程安全	特点	时间复杂度（常见操作）
`ArrayList`	动态数组（Object[]）	❌ 否	随机访问快，插入/删除慢（中间位置）	get/set: O(1) add/remove（尾部）: O(1) add/remove（中间）: O(n)
`LinkedList`	双向链表	❌ 否	插入/删除快，随机访问慢	get(i): O(n) add/remove（首尾）: O(1) add/remove（中间）: O(n)（需遍历定位）
`Vector`	动态数组	✅ 是（方法加 synchronized）	老旧，性能差，已不推荐	同 ArrayList，但慢
`CopyOnWriteArrayList`	写时复制数组	✅ 是	读多写少场景，写操作创建新副本	读: O(1) 写: O(n)（复制整个数组）

使用建议：

优先用 ArrayList：90% 场景足够；
频繁在首尾增删 → 考虑 LinkedList（但实际因缓存局部性，ArrayList 仍可能更快）；
高并发读多写少 → CopyOnWriteArrayList。

// 示例：ArrayList vs LinkedList
List<String> list1 = new ArrayList<>();   // 推荐默认选择
List<String> list2 = new LinkedList<>();  // 仅当频繁首尾操作且数据量大时考虑

三、Set 接口及实现类

实现类	底层数据结构	是否有序	是否允许 null	时间复杂度（add/contains/remove）
`HashSet`	HashMap（key 存元素，value 为 dummy）	❌ 无序	✅ 允许一个 null	O(1) 平均，最坏 O(n)
`LinkedHashSet`	LinkedHashMap	✅ 按插入顺序	✅ 允许一个 null	O(1)
`TreeSet`	红黑树（TreeMap）	✅ 自然排序或 Comparator	❌ 不允许 null（会抛 NPE）	O(log n)

特点说明：

HashSet：基于哈希，最快，但无序；
LinkedHashSet：在 HashSet 基础上维护插入顺序（额外维护双向链表）；
TreeSet：自动排序，支持范围查询（如 subSet, headSet）。

Set<Integer> set = new TreeSet<>();
set.add(3); set.add(1); set.add(2);
System.out.println(set); // [1, 2, 3] —— 自动排序

四、Map 接口及实现类

实现类	底层数据结构	是否有序	是否允许 null key/value	线程安全	时间复杂度
`HashMap`	数组 + 链表/红黑树（JDK 8+）	❌ 无序	✅ key 一个 null，value 多个 null	❌ 否	O(1) 平均
`LinkedHashMap`	HashMap + 双向链表	✅ 插入顺序 / 访问顺序	✅ 同 HashMap	❌ 否	O(1)
`TreeMap`	红黑树	✅ key 自然排序或 Comparator	❌ key 不能为 null	❌ 否	O(log n)
`Hashtable`	哈希表（类似老版 HashMap）	❌ 无序	❌ key/value 都不能为 null	✅ 是	O(1)
`ConcurrentHashMap`	分段锁（JDK 7） / CAS + synchronized（JDK 8+）	❌ 无序	✅ key 一个 null（JDK 8+ 允许？实际不允许！）	✅ 是	O(1)

⚠️ 重要纠正：
ConcurrentHashMap 不允许 key 或 value 为 null！
原因：null 无法区分“未找到”还是“值就是 null”，在并发环境下语义模糊。

LinkedHashMap 的两种顺序：

// 按插入顺序（默认）
new LinkedHashMap<>();

// 按访问顺序（可用于 LRU 缓存）
new LinkedHashMap<>(16, 0.75f, true);

五、Queue 与 Deque

类	底层	特点	常用方法
`LinkedList`	双向链表	实现 `List`, `Deque`, `Queue`	`offer()`, `poll()`, `peek()`
`ArrayDeque`	循环数组	推荐替代 Stack/LinkedList 作队列	同上
`PriorityQueue`	二叉堆	按优先级出队（最小堆）	`offer()`, `poll()` 返回最小元素

✅ 最佳实践：
用 ArrayDeque 代替 Stack（Stack 继承 Vector，性能差）；
优先级队列用 PriorityQueue。

// LIFO 栈（推荐）
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
System.out.println(stack.pop()); // 2

// FIFO 队列
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
System.out.println(queue.poll()); // 1

六、线程安全集合（并发集合）

非线程安全	线程安全替代方案	说明
`ArrayList`	`Collections.synchronizedList(new ArrayList<>())` `CopyOnWriteArrayList`	前者全局锁，后者写时复制
`HashSet`	`Collections.synchronizedSet(new HashSet<>())` `CopyOnWriteArraySet`
`HashMap`	`Collections.synchronizedMap(new HashMap<>())` `ConcurrentHashMap`	优先用 `ConcurrentHashMap`
`TreeMap`	`ConcurrentSkipListMap`	基于跳表，并发有序 Map

🔥 重点：ConcurrentHashMap 是高性能并发 Map 的首选！

七、集合工具类与扩展

1. `Collections` 工具类

// 创建不可变集合（Java 9+ 更推荐用 of()）
List<String> immutable = Collections.unmodifiableList(list);

// 同步包装
List<String> syncList = Collections.synchronizedList(new ArrayList<>());

// 排序、查找、填充等
Collections.sort(list);
Collections.max(list);
Collections.fill(list, "default");

2. Java 9+ 不可变集合工厂方法（推荐！）

List<String> list = List.of("a", "b", "c");         // 不可变
Set<String> set = Set.of("x", "y");                 // 不可变
Map<String, Integer> map = Map.of("age", 25);       // 不可变

✅ 特点：简洁、安全、性能好（内部优化存储）。

3. 自定义集合（继承或组合）

一般不建议继承 ArrayList 等，而是组合 + 委托；
如需扩展功能，可实现对应接口或使用装饰器模式。

八、集合选型决策树（参考）

Java-集合

一、集合框架整体架构

核心接口关系图

二、List 接口及实现类

使用建议：

三、Set 接口及实现类

特点说明：

四、Map 接口及实现类

LinkedHashMap 的两种顺序：

五、Queue 与 Deque

六、线程安全集合（并发集合）

七、集合工具类与扩展

1. Collections 工具类

2. Java 9+ 不可变集合工厂方法（推荐！）

3. 自定义集合（继承或组合）

八、集合选型决策树（参考）

评论区

Java-集合

1. `Collections` 工具类