Java 集合

集合框架概述

Java 集合框架主要围绕两个关键接口组织：Collection 和 Map。 Collection 接口有几个专门的子接口，包括 List、Set 和 Queue。这些接口中的每一个都有具有不同性能特征的多个实现。

来源

核心集合接口

Collection 接口

Collection 是集合层次结构中的根接口。它用作对象的容器，并表示一组称为元素的对象的集合。它不实现任何具体的数据结构，但为更具体的集合类型提供了基础。

List 接口

List 接口扩展了 Collection，表示一个有序的元素集合，允许重复值。列表维护插入顺序并允许对元素进行位置访问。

主要实现

ArrayList：基于动态数组
LinkedList：实现为双向链表
Vector：基于数组的线程安全实现（遗留类）

Set 接口

Set 接口扩展了 Collection，表示一个不能包含重复元素的集合。主要实现有

HashSet：基于 HashMap，没有排序保证
LinkedHashSet：维护插入顺序，基于 LinkedHashMap
TreeSet：按排序顺序维护元素，基于红黑树

Queue 和 Deque 接口

Queue 表示一个为在处理之前保存元素而设计的集合，通常按 FIFO（先进先出）顺序。

Deque（双端队列）扩展了 Queue，并支持在两端进行插入和删除。

主要实现

PriorityQueue：元素按优先级排序而非 FIFO
ArrayDeque：实现为可变大小的数组
LinkedList：也实现了 Deque

Map 接口

Map 并非真正的集合，但包含在集合框架中。它将键映射到值，不允许重复键。主要实现有

HashMap：O(1) 操作，无排序保证
LinkedHashMap：维护插入顺序
TreeMap：按排序顺序维护键
Hashtable：线程安全的遗留实现

来源

底层数据结构

ArrayList

ArrayList 使用内部的 Object[] 数组来存储元素。当数组填满时，会分配一个更大的新数组，并将所有元素复制过去。这提供了 O(1) 的随机访问，但插入/删除操作可能为 O(n)。

链表

LinkedList 实现为双向链表，其中每个元素都维护着指向前一个和后一个元素的引用。

HashMap

HashMap 使用桶数组，每个桶包含一个链表或条目的红黑树（Java 8+）。该结构使用哈希码来确定将条目放置在哪个桶中，并处理冲突。

在 Java 8+ 中，当一个桶中的链表超过阈值（通常是 8 个条目）时，它会被转换为红黑树，以将最坏情况的性能从 O(n) 提高到 O(log n)。

HashSet

HashSet 在内部使用 HashMap 实现，其中元素作为键存储，并带有一个共享的虚拟值。

来源

性能特征

列表实现

操作	ArrayList	链表
访问	O(1)	O(n)
在末尾插入	O(1) 摊销	O(1)
头插	O(n)	O(1)
按索引插入	O(n)	O(n)
尾删	O(1)	O(1)
头删	O(n)	O(1)
按索引删除	O(n)	O(n)
搜索	O(n)	O(n)

HashMap vs TreeMap

操作	HashMap	TreeMap
获取	O(1)	O(log n)
放置	O(1)	O(log n)
删除	O(1)	O(log n)
包含	O(1)	O(log n)
下一阶段	O(h/n)	O(log n)
顺序	无	按键排序

来源

实现细节

ArrayList 实现

ArrayList 是 List 接口的可调整大小的数组实现。它提供常数时间的位置访问，并且对大多数操作都很高效。

主要实现细节

默认初始容量：10
增长策略：容量达到时增加约 50%
随机访问：O(1)，由于数组结构
内存开销：数组中有额外的未使用容量
实现了 RandomAccess 接口，表示支持快速随机访问

来源

HashMap实现

HashMap 在假设哈希函数良好的情况下，为基本操作（get 和 put）提供常数时间性能。

主要实现细节

默认初始容量：16
默认负载因子：0.75
桶结构
- Java 7 中：链表
- Java 8+ 中：链表 + 红黑树
当桶包含 8 个及以上条目且数组大小至少为 64 时，会发生树转换
树转换将最坏情况性能从 O(n) 提高到 O(log n)
容量始终是 2 的幂，以优化哈希计算

来源

选择正确的集合

List：ArrayList vs LinkedList

当以下情况时使用 ArrayList
- 频繁进行随机访问
- 初始化后列表大小变化不大
- 经常进行顺序访问
当以下情况时使用 LinkedList
- 频繁在开头或中间进行插入/删除
- 不需要随机访问
- 实现堆栈或队列行为

Map：HashMap vs TreeMap vs LinkedHashMap

当以下情况时使用 HashMap
- 顺序无关紧要
- 需要最大查找性能
当以下情况时使用 TreeMap
- 条目需要按键排序
- 需要查找最接近的匹配项、条目范围
当以下情况时使用 LinkedHashMap
- 插入顺序或访问顺序很重要
- 需要可预测的迭代顺序

Set：HashSet vs TreeSet vs LinkedHashSet

选择原则与相应的 Map 实现相同

来源

常见陷阱和最佳实践

线程安全

JCF 中的大多数集合实现都不是线程安全的。对于并发访问

使用线程安全的替代方案，如 ConcurrentHashMap
通过 Collections.synchronizedXXX 方法使用线程安全的包装器
使用外部同步块

快速失败 vs 安全失败迭代

快速失败：ArrayList 和 HashMap 等标准集合使用快速失败迭代器，如果在迭代期间修改了集合，则会抛出 ConcurrentModificationException
安全失败：ConcurrentHashMap 等并发集合使用安全失败迭代器，它们作用于集合的副本，不会抛出异常

容量管理

如果可能，使用适当的容量初始化集合
一次添加大量元素时使用 ensureCapacity 方法
选择实现时考虑内存开销

其他技巧

使用 isEmpty() 而不是检查 size() == 0
不要过度使用 LinkedList，因为开销通常会抵消其好处
对于线程安全操作，优先使用 ConcurrentHashMap 而非 Hashtable
尽量避免在集合中存储 null 值

来源

集合迭代

增强 for 循环

Iterator 模式

Stream API (Java 8+)

来源

docs/java/collection/java-collection-questions-01.md258-322

总结

Java 集合框架提供了用于存储和操作对象组的全面接口和实现。通过了解每种集合类型的底层数据结构、性能特征和适当的用例，开发人员可以做出明智的决策，以优化其应用程序的性能和可维护性。

选择集合时，请考虑

将最频繁执行的操作
应用程序的内存限制
是否需要线程安全
顺序保持的重要性
预期的集合大小和增长模式

通过正确的集合选择和恰当的使用模式，Java Collections Framework 可以显著提高代码的可读性、性能和可维护性。