选择Java集合实现的经验法则是什么？

Question

有没有一个选择Java集合接口（如List、Map或Set）不同实现的好方法？

例如，通常在什么情况下我会更喜欢使用Vector或ArrayList、Hashtable或HashMap等。

- hydeph

Answer 1

我非常喜欢Sergiy Kovalchuk的博客中的这张备忘单，但不幸的是它已经下线了。然而，Wayback Machine有一份历史副本：

更加详细的是Alexander Zagniotov的流程图，也因此离线，因此也是博客的历史副本：

“这篇博客摘自评论中提出的问题：‘这份速查表没有包括像WeakHashMap、LinkedList等很少使用的类，因为它们被设计用于非常特定或者奇异的任务，在99%的情况下不应该选择它们。’”

- ChrLipp

---

易于理解和记忆。 - Imran Ali

ArrayList和LinkedList都是List接口的实现。这意味着它们保留插入顺序。那么为什么你更喜欢LinkHashSet而不是ArrayList来实现这个目的呢？ - Alexius DIAKOGIANNIS

我刚刚参考了备忘单，但是为了回答你的问题：LinkHashSet 的决策是值、无重复项、搜索和插入顺序。因此，与 ArrayList 的区别在于“无重复项”和搜索决策。ArrayList 允许重复项，如果您搜索该值，则搜索时间复杂度为 O(n)。 - ChrLipp

链表丢失。 - Arun Raaj

如先前所述，这份备忘单是错误的。至少在LinkedList方面是如此。如果我只有值，这些值可能包含重复项，那么ArrayList并不是一个显而易见的选择。因为我可能根本不需要随机访问，我要做的就是在循环中添加元素，而LinkedList会更优秀。 - LLL

以下是博客中提到的内容：“这份备忘单不包括像WeakHashMap、LinkedList等很少使用的类，因为它们被设计用于非常特定或奇特的任务，并且在99%的情况下不应该选择它们。” - Rchauhan

Answer 2

我假设您已经从以上答案中了解了List、Set和Map的区别。为什么要选择它们的实现类又是另一回事。例如：

List：

1. ArrayList 在检索上很快，但在插入方面很慢。它适用于大量读取但不大量插入/删除的实现。它将其数据保存在一个连续的内存块中，因此每次需要扩展时，它都会复制整个数组。
2. LinkedList 在检索上很慢，但在插入方面很快。它适用于大量插入/删除但不大量读取的实现。它不将整个数组保存在一个连续的内存块中。

Set：

1. HashSet 不保证迭代顺序，因此是最快的集合。它有很高的开销，比ArrayList慢，因此除非有大量数据并且哈希速度成为因素，否则不应该使用它。
2. TreeSet 保持数据有序，因此比HashSet慢。

Map： HashMap和TreeMap的性能和行为与Set实现相同。

Vector和Hashtable不应该使用。它们是在新的Collection层次结构发布之前同步实现，因此速度较慢。如果需要同步，请使用Collections.synchronizedCollection()。

- Jonathan

---

你应该区分使用 add(int, E) 在给定的索引位置插入和使用 add(E) 在任何位置插入的区别。ArrayList 在数组末尾添加元素不慢（除非需要扩展支撑数组时），而LinkedList在后一种情况下也不会慢。 - artbristol

Answer 3

我总是根据具体情况做出决策，例如：

• 我是否需要保持排序？
• 是否会有空键/值或重复项？
• 它是否将被多个线程访问？
• 我是否需要键/值对？
• 我是否需要随机访问？

接着我会拿出我方便的第五版《Java核心技术》并比较大约20个选项。在第五章中，它有一些漂亮的小表格可以帮助人们找到合适的选择。

好吧，也许如果我知道一个简单的ArrayList或HashSet会解决问题，我就不会再查了。；）但是，如果我的使用场景稍微有点复杂，我肯定会翻书。顺便说一下，我认为Vector应该是“老古董”了-我已经好几年没用过了。

- Stu Thompson

---

为什么这被选为最佳答案？它只是提了一堆问题然后引用了一本书。 - Beefster

Answer 4

就理论而言，大O符号是有用的折衷方案，但在实践中几乎从来不重要。

在真实世界的基准测试中，ArrayList即使对于大型列表和“靠近前面的大量插入”等操作也会优于LinkedList。学者们忽略了真正算法的常数因子可能会压倒渐近曲线这一事实。例如，链表需要为每个节点分配额外的对象内存，这意味着创建节点更慢，内存访问特性也非常糟糕。

我的规则是：

1. 始终从ArrayList和HashSet和HashMap 开始（即不使用 LinkedList或TreeMap）。
2. 类型声明应始终是一个接口（即List，Set，Map），因此如果分析器或代码审查证明其他方式更好，您可以更改实现而不会破坏任何内容。

- Jason Cohen

---

请注意，ChrLipp的图表中甚至没有LinkedList选项，而其他选项实际上只取决于您需要什么顺序。不过我确实喜欢这个答案。 - Beefster

Answer 5

关于你的第一个问题...

List，Map和Set各有不同的用途。我建议阅读Java集合框架的文档：http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html。

更具体地说：

• 如果你需要类似数组的数据结构，并且需要遍历元素，则使用List
• 如果你需要类似字典的东西，则使用Map
• 如果你只需要确定某个东西是否属于集合，则使用Set。

关于你的第二个问题...

Vector和ArrayList的主要区别在于前者是同步的，后者不是同步的。您可以阅读《Java并发实践》了解更多关于同步的知识。(https://rads.stackoverflow.com/amzn/click/com/0321349601)。

Hashtable (注意T不是大写字母) 和HashMap之间的区别类似，前者是同步的，后者不是同步的。

我认为没有什么经验法则可以优先选择一种实现方式，这真的取决于您的需求。

- Zizzencs

Answer 6

对于非排序的情况，最好的选择十有八九是：ArrayList、HashMap、HashSet。

Vector和Hashtable是同步的，因此可能会慢一些。很少有需要同步实现的情况，即使需要，它们的接口也不够丰富，无法发挥其同步作用。在Map的情况下，ConcurrentMap添加了额外的操作，使接口变得有用。ConcurrentHashMap是ConcurrentMap的一个很好的实现。

LinkedList几乎从来不是一个好主意。即使你要做很多插入和删除，如果你使用索引来指示位置，那么就需要通过列表迭代来找到正确的节点。ArrayList几乎总是更快的选择。

对于Map和Set，哈希变量比树/排序变量更快。哈希算法往往具有O(1)的性能，而树则为O(log n)。

- Tom Hawtin - tackline

Answer 7

好的，这取决于你需要什么。一般的指导原则如下：

列表（List）是一个集合，其中数据按插入顺序排列，每个元素都有索引。

集合（Set）是一组没有重复元素的元素袋（如果重新插入相同的元素，则不会添加）。数据没有顺序概念。

映射（Map）通过它们的键访问和写入数据元素，键可以是任何可能的对象。 来源：https://dev59.com/3GEh5IYBdhLWcg3w0WVP#21974362 要了解更多关于Java集合的信息，请查看此文章。

- Johnny

Answer 8

列表允许重复的项，而集合只允许一个实例。当需要执行查找时，我会使用Map。对于具体的实现，有保持顺序的Map和Set的变化，但主要取决于速度。我倾向于在相当小的列表中使用ArrayList，在相当小的集合中使用HashSet，但有许多实现（包括您自己编写的任何实现）。HashMap在映射中非常常见。如果超过了“相当小”的范围，就必须开始担心内存问题，因此算法会更加具体。如果您对硬数字感兴趣，此页面有很多动画图像以及测试LinkedList vs. ArrayList的示例代码。

编辑：我希望以下链接能够证明这些东西只是工具箱中的项目，你只需要考虑自己的需求：请查看Map、List和Set的Commons-Collections版本。

- Joe Liversedge

Answer 9

正如其他答案所建议的那样，根据用例不同，使用正确的集合有不同的方案。我列出了一些要点：

ArrayList：

• 大多数情况下，你只需要存储或迭代“一堆东西”，然后再迭代它们。由于是基于索引的，因此迭代速度更快。
• 每当创建ArrayList时，都会为其分配一定数量的内存，一旦超过，就会复制整个数组。

LinkedList：

• 它使用双向链表，因此插入和删除操作将很快，因为它只会添加或删除一个节点。
• 检索速度较慢，因为它必须遍历所有节点。

HashSet：

• 对项目进行其他二元决策，例如“该项目是英语单词”、“该项目是否在数据库中？”、“该项目是否属于此类别？”等。

• 记住“您已经处理过哪些项目”，例如在进行网络爬虫时；

HashMap：

• 用于需要说“对于给定的X，Y是什么”的情况。它通常用于实现内存缓存或索引，即键值对。例如：对于给定的用户ID，他们的缓存名称/用户对象是什么？
• 执行查找时始终使用HashMap。

Vector和Hashtable是同步的，因此速度稍慢。如果需要同步，请使用Collections.synchronizedCollection()。有关排序集合，请查看此处。希望这可以帮助到你。

- Vikas

Answer 10

使用Map进行键值对配对

对于键-值跟踪，使用Map实现。

例如，跟踪哪个人在周末的哪一天工作。因此，我们希望将一个DayOfWeek对象映射到一个Employee对象。

Map < DayOfWeek , Employee > weekendWorker = 
    Map.of( 
        DayOfWeek.SATURDAY , alice ,
        DayOfWeek.SUNDAY , bob
    )
;

在选择Map实现之一时，有几个方面需要考虑。这些包括：并发性、对键和/或值中的NULL值的容忍度、迭代键时的顺序、按引用与内容跟踪以及文字语法的方便性。

这是我制作的一张图表，显示了Java 11捆绑的十种Map实现的各个方面。

- Basil Bourque