如何在Java中选择合适的集合
如何在Java中选择合适的集合
在本教程中，我们将讨论如何在Java库中选择适当的集合接口和类。我们跳过了诸如_Vector_、_Stack_和_Hashtable_等遗留集合，因为我们需要避免使用它们，而转而使用新的集合。并发集合值得单独讨论，因此我们也不在此讨论它们。
2. Java库中的集合接口
在尝试有效使用它们之前，了解Java库中集合接口和类的组织结构非常有用。_Collection_接口是所有集合接口的根。List、Set_和_Queue_接口扩展了_Collection。
在Java库中，映射（Maps）不被视为常规集合，因此_Map_接口不扩展_Collection_。这是Java库中接口关系的图表：
任何具体的集合实现（集合类）都是从集合接口派生的。集合类的语义由它们的接口定义，因为具体的集合为它们父接口定义的操作提供了具体的实现。因此，我们需要在选择适当的集合类之前，先选择正确的集合接口。
3. 选择正确的集合接口
选择正确的集合接口是相对直接的。实际上，下面的图表显示了一个逻辑接口选择流程：
总结来说，当元素的插入顺序很重要并且有重复元素时，我们使用列表（lists）。当元素被视为一组对象，没有重复项，且插入顺序不重要时，我们使用集合（sets）。
队列（queues）用于需要_LIFO_（后进先出）、FIFO（先进先出）或按优先级移除语义的情况，最后，当需要键值对关联时，我们使用映射（maps）。
4. 选择正确的集合实现
下面我们可以找到按它们实现的接口分类的集合类的比较表。比较是基于常见操作及其性能进行的。具体来说，操作的性能是使用大O符号估计的。可以在Java集合操作的基准测试中找到更实用的操作持续时间指南。
4.1. 列表
让我们从列表比较表开始。列表的常见操作包括添加和删除元素、通过索引访问元素、遍历元素和查找元素：
| 列表比较表 | 在开头添加/删除元素 | 在中间添加/删除元素 | 在末尾添加/删除元素 | 获取第i个元素（随机访问） | 查找元素 | 遍历顺序 |
|---|---|---|---|---|---|---|
| ArrayList | O(n) | O(n) | O(1) | O(1) | O(n), 如果排序了则为_O(log(n))_ | 按插入顺序 |
| LinkedList | O(1) | O(1) | O(1) | O(n) | O(n) | 按插入顺序 |
如我们所见，_ArrayList_擅长在末尾添加和删除元素，以及具有对元素的随机访问。相反，它不擅长在任意位置添加和删除元素。同时，_LinkedList_擅长在任何位置添加和删除元素。然而，它不支持真正的_O(1)随机访问。所以，关于列表，除非我们需要在任何位置快速添加和删除元素，否则默认选择是_ArrayList。
4.2. 集合
对于集合，我们感兴趣的是添加和删除元素、遍历元素和查找元素：
| 集合比较表 | 添加元素 | 删除元素 | 查找元素 | 遍历顺序 |
|---|---|---|---|---|
| HashSet | 平均_O(1)_ | 平均_O(1)_ | O(1) | 随机，由哈希函数分散 |
| LinkedHashSet | 平均_O(1)_ | 平均_O(1)_ | O(1) | 按插入顺序 |
| TreeSet | O(log(n)) | O(log(n)) | O(log(n)) | 排序，根据元素比较标准 |
| EnumSet | O(1) | O(1) | O(1) | 根据枚举值的定义顺序 |
如我们所见，默认选择是_HashSet_集合，因为它在所有支持的操作中都非常快。此外，如果元素的插入顺序也很重要，我们选择_LinkedHashSet_。它基本上是_HashSet_的扩展，通过使用内部的链表结构来跟踪元素的插入顺序。
如果需要元素被排序，并且在添加和删除元素时需要保持排序顺序，那么我们应该选择_TreeSet_。
如果集合中的元素只是单个枚举类型的枚举值，那么最明智的选择是_EnumSet_。
4.3. 队列
队列可以分为两组：
- LinkedList, ArrayDeque – 队列接口的实现可以作为栈、队列和双端队列数据结构。通常，_ArrayDeque_比_LinkedList_更快。因此它是默认选择。
- PriorityQueue – 队列接口的实现，由二叉堆数据结构支持。用于快速（O(1)）检索具有最高优先级的元素。添加和删除操作在_O(log(n))_时间内完成。
4.4. 映射
与集合类似，我们考虑映射的操作：添加和删除元素、遍历元素和查找元素：
| 映射比较表 | 添加元素 | 删除元素 | 查找元素 | 遍历顺序 |
|---|---|---|---|---|
| HashMap | 平均_O(1)_ | 平均_O(1)_ | O(1) | 随机，由哈希函数分散 |
| LinkedHashMap | 平均_O(1)_ | 平均_O(1)_ | O(1) | 按插入顺序 |
| TreeMap | O(log(n)) | O(log(n)) | O(log(n)) | 排序，根据元素比较标准 |
| EnumMap | O(1) | O(1) | O(1) | 根据枚举值的定义顺序 |
映射的选择逻辑与集合的选择逻辑类似：我们默认使用_HashMap_，如果插入顺序也很重要，则使用_LinkedHashMap_，排序时使用_TreeMap_，当键属于特定枚举类型的值时使用_EnumMap_。
最后，有两个_Map_接口的实现具有非常特定的应用：IdentityHashMap_和_WeakHashMap。
5. 具体集合选择图表
我们可以扩展选择适当集合接口的图表，以选择具体的集合实现：
6. 结论
在本文中，我们了解了Java库中的集合接口和集合类。此外，我们提出了选择正确接口和实现的方法。