我应该使用哪个Java集合类？

Question

在这个问题中，如何在C++11中高效选择标准库容器？是一个很方便的流程图，用于选择C++集合。

我认为这对于不确定应该使用哪种集合的人来说是一个有用的资源，所以我尝试寻找一个类似的Java流程图，但未能找到。

有哪些资源和“备忘单”可帮助人们在编写Java代码时选择正确的集合？人们如何知道应该使用哪些List、Set和Map实现？

- Tim B

---

书籍《Java泛型与集合》（Naftalin＆Wadler）有一章关于此主题。 - Christophe Roussy

这里有很多好的答案，但我没有看到任何关于“大O符号”的讨论。确定使用哪个“集合”时，“大O符号”不是非常有用吗？https://dev59.com/P3RB5IYBdhLWcg3wpotm - SedJ601

@SedJ601 我不会详细解释BigO的后果，但我的解释中已经涵盖了它。算法的顺序并不是一切，因为它不考虑固定成本。LinkedList与ArrayList的成本开销巨大 - 因此，即使对于在链表中为O(1)而在ArrayList中为O(n)的操作，您需要一个非常大的列表才能超过另一个。 - Tim B

Answer 1

由于我找不到类似的流程图，所以决定自己制作一张。

本流程图不尝试涵盖同步访问、线程安全等内容或旧集合，但它确实涵盖了3个标准的Set、3个标准的Map和2个标准的List。

_{此图片是为了回答而创建的，并获得知识共享署名4.0国际许可证。最简单的归属方式是链接到该问题或该答案。}

其他资源

可能最有用的其他参考是来自Oracle文档的以下页面，其中描述了每个Collection。

HashSet vs TreeSet

关于何时使用HashSet或TreeSet的详细讨论在这里： Hashset vs Treeset

ArrayList vs LinkedList

详细讨论：When to use LinkedList over ArrayList?

- Tim B

---

很好！但我必须不同意你的LinkedList与ArrayList决策。首先，如果列表的大小相当大，则LinkedList更可取。LinkedList对每个元素都有开销，因此在内存消耗方面，在渐近意义上，它比ArrayList更糟糕。此外，如果大多数访问在列表末尾，那么ArrayList更可取，因为它提供了常数时间的随机元素访问。访问LinkedList的第n个元素是一个O(n)操作。实际上，使用链表的决定几乎总是“不”。 - Matt Ball

@MattBall 我大部分同意你的观点。然而，Java的LinkedList是一个双向链表，因此在开头和结尾的访问都很快。你会注意到，在上面的所有分支中，三个问题都必须回答“是”，我才会建议使用LinkedList - 换句话说，我同意你的观点，在大多数情况下答案是否定的。像队列和双端队列这样需要不断添加和删除列表末尾元素的情况是LinkedList的好用例。 - Tim B

@MattBall 内存使用情况更加棘手，因为虽然 LinkedList 每个元素使用的内存更多...但是 ArrayList 从不释放内存。这意味着如果您有一个列表，有时会增长到巨大的大小，但通常很小，那么 ArrayList 将提供更差的内存性能。与其包含的元素相比，List 本身的内存开销通常（虽然不总是）很小。 - Tim B

Map<K,V> isn't the part of java.util.collection - Mehraj Malik

@MehrajMalik 嗯，我同意标签不太清晰。我的意思是java.util中的Collection，即java.util.在此插入集合名称。 - Tim B

Answer 2

非并发、非同步集合主要概述

Collection：一个表示无序“包”或称为“元素”的接口。下一个元素是未定义的（随机的）。

• Set：表示没有重复项的Collection接口。
  • HashSet：由Hashtable支持的Set。在不考虑排序时具有最快和最小的内存使用情况。
  • LinkedHashSet：在插入顺序中关联元素的HashSet。下一个元素是最近插入的元素。
  • TreeSet：元素由Comparator（通常是自然排序）排序的Set。内存使用最慢最大，但对于基于比较器的排序是必要的。
  • EnumSet：一种极其快速和高效的Set，专门定制给单个枚举类型使用。
• List：表示一个Collection，其中的元素是有序的，并且每个元素都有一个数字索引表示其位置，其中零是第一个元素，而(length - 1) 是最后一个。
  • ArrayList：由数组支持的List，其中该数组具有至少与元素数量（列表的“大小”）相同的长度（称为“容量”）。当大小超过容量时（添加第(capacity + 1)个元素时），数组将以新的容量(new length * 1.5)重新创建--这个过程很快，因为它使用了System.arrayCopy()。删除、插入/添加元素需要将所有相邻的元素（右侧）移动到该空间中或从该空间中移出。访问任何元素都很快，因为它只需要计算(element-zero-address + desired-index * element-size)来找到其位置。在大多数情况下，优先使用ArrayList而非LinkedList。
  • LinkedList：一种由一组对象支持的列表，每个对象都连接到其“前一个”和“后一个”邻居。 LinkedList也是Queue 和 Deque。访问元素是从第一个或最后一个元素开始，然后遍历，直到达到所需的索引。插入和删除操作，在通过遍历达到所需的索引后，只需要重新映射仅与新元素相邻的链接或绕过现在已经被删除的元素即可。
• Map: 表示一个Collection，其中每个元素都具有一个标识性的“键”——每个元素都是一个键值对。
  • HashMap：键是无序的Map，由Hashtable支持。
  • LinkedhashMap：键按插入顺序排序。
  • TreeMap： 键按Comparator（通常是自然排序）排序的Map。
• Queue：表示一种集合，元素通常从一个端添加，从另一个端移除（FIFO：先进先出）。
• Stack：表示一种集合，元素通常从同一端添加（推入），并从该端移除（弹出）（LIFO：后进先出）。
• Deque：缩写为“双端队列”，通常发音为“deck”。它是一个链表，通常只能从两端添加和读取（而不是中间）。

基本集合图示：

将元素插入 ArrayList 和 LinkedList 进行比较：

- aliteralmind

---

最简洁的总结，任何人都可以在这里得到 :) - roottraveller

Answer 3

这里有一张更简单的图片。故意简化了！

1. 集合 是指存储数据的任何东西，称为“元素”（相同类型）。没有更具体的假设。

2. 列表 是一个带有索引的数据集合，其中每个元素都有一个索引。类似于数组，但更灵活。

   列表中的数据保留插入顺序。

   典型操作：获取第n个元素。

3. 集合 是一个元素的包，每个元素只出现一次（使用它们的equals()方法区分元素）。

   集合中的数据主要存储以了解存在哪些数据。

   典型操作：查看列表中是否存在元素。

4. 映射表 类似于列表，但是您可以通过它们的键而不是整数索引访问它们，该键是任何对象。就像PHP中的数组:)

   Map中的数据可通过其键进行搜索。

   典型操作：通过其ID获取元素（其中ID是任何类型，而不仅仅是int，如列表的情况）。

区别

• Set vs. Map: 在 Set 中，您通过元素本身进行搜索，而在 Map 中，您通过它们的键进行搜索。

  N.B. 标准库中的 Sets 确实是按照这种方式实现的：一个 Map，其中键是 Set 元素本身，并带有一个虚拟值。

• List vs. Map: 在 List 中，您通过其 int 索引（在 List 中的位置）访问元素，而在 Map 中，您通过其任意类型的键（通常为 ID）访问元素。

• List vs. Set: 在 List 中，元素受其位置限制并且可以重复，而在 Set 中，元素仅存在（或不存在）且唯一（在 equals() 的含义下，或对于 SortedSet 的 compareTo()）

- Honza Zidek

Answer 4

Map（映射）

如果选择使用Map，我制作了以下表格总结Java 11中附带的十种实现的特点。

- Basil Bourque

Answer 5

很简单：如果您需要将值与映射到它们的键一起存储，请使用Map接口，否则对于可能重复的值，请使用List，最后如果您不想在集合中有重复的值，请使用Set接口。

这里是完整的解释 http://javatutorial.net/choose-the-right-java-collection，包括流程图等。

- filip_j

Answer 6

常见集合，常见集合

- Aliaksandr Shpak

---

HashMap 不是一个接口。 - Basil Bourque