java - 选择 Java 集合实现的经验法则？

Question

任何人都有一个很好的经验法则来选择 Java Collection 接口的不同实现，如 List、Map 或 Set？

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

Answer 1

我真的很喜欢 Sergiy Kovalchuk 博客条目中的这张备忘单，但不幸的是它已离线。但是，Wayback Machine 有一个历史副本：

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

关于评论中提出的问题的博客摘录：“这份备忘单不包括很少使用的类，如 WeakHashMap、LinkedList 等，因为它们是为非常特定或奇异的任务而设计的，不应该在 99% 的情况下选择。”

Answer 2

我假设您从上述答案中知道 List、Set 和 Map 之间的区别。为什么你会在他们的实现类之间进行选择是另一回事。例如：

清单：

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

放：

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

Map： HashMap 和 TreeMap 的性能和行为与 Set 实现是平行的。

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

Answer 3

我总是根据用例逐案做出这些决定，例如：

• 我需要保留订单吗？
• 我会有空键/值吗？重复？
• 是否会被多个线程访问
• 我需要一个键/值对吗
• 我需要随机访问吗？

然后我总结了我方便的第 5 版Java并比较了大约 20 个选项。它在第五章中有很好的小表格，可以帮助人们弄清楚什么是合适的。

好吧，也许如果我立即知道一个简单的 ArrayList 或 HashSet 可以解决问题，我就不会全部查找了。;) 但如果我的预期用途有任何复杂的地方，你敢打赌我在书中。顺便说一句，我虽然 Vector 应该是“老帽子”——我已经好几年没用过了。

Answer 4

理论上存在有用的 Big-Oh权衡，但实际上这些几乎无关紧要。

在现实世界的基准测试中，即使是大列表和“靠近前面的大量插入”之类的操作，ArrayList它的表现也很出色。LinkedList学者们忽略了一个事实，即真正的算法具有可以压倒渐近曲线的常数因素。例如，链表需要为每个节点分配额外的对象，这意味着创建节点的速度较慢，内存访问特性也非常差。

我的规则是：

1. 总是从 ArrayList 和 HashSet 和 HashMap 开始（即不是 LinkedList 或 TreeMap）。
2. 类型声明应该始终是一个接口（即 List、Set、Map），因此如果分析器或代码审查证明不是这样，您可以在不破坏任何内容的情况下更改实现。

Answer 5

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

List、Map 和 Set 有不同的用途。我建议在http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html阅读有关 Java 集合框架的信息。

更具体一点：

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

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

Vector和ArrayList的主要区别在于前者是同步的，后者是不同步的。您可以在Java Concurrency in Practice中阅读有关同步的更多信息。

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

我想说的是，没有经验法则可以选择一种或另一种实现，这实际上取决于您的需求。

Answer 6

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

Vector 和 Hashtable 是同步的，因此可能会慢一些。您很少需要同步实现，并且当您这样做时，它们的接口不够丰富，以至于它们的同步有用。在 Map 的情况下，ConcurrentMap 添加了额外的操作以使接口变得有用。ConcurrentHashMap 是 ConcurrentMap 的一个很好的实现。

LinkedList 几乎从来都不是一个好主意。即使您正在执行大量插入和删除操作，如果您使用索引来指示位置，那么也需要遍历列表以找到正确的节点。ArrayList 几乎总是更快。

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

Answer 7

列表允许重复项，而集合只允许一个实例。

每当我需要执行查找时，我都会使用 Map。

对于具体的实现，Maps 和 Sets 有一些保持顺序的变化，但很大程度上归结为速度。我倾向于将 ArrayList 用于相当小的列表，将 HashSet 用于相当小的集合，但是有很多实现（包括您自己编写的任何实现）。HashMap 对于 Map 来说非常常见。除了“合理的小”之外，您还必须开始担心内存，以便在算法上更加具体。

如果您对硬数字感兴趣，此页面包含大量动画图像以及测试 LinkedList 与 ArrayList 的示例代码。

编辑：我希望以下链接演示这些东西实际上只是工具箱中的项目，您只需要考虑您的需求是什么：请参阅Map、List和Set的 Commons-Collections 版本。

Answer 8

正如其他答案中所建议的那样，根据用例，有不同的场景可以使用正确的集合。我列举几点，

数组列表：

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

链表：

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

哈希集：

• 对某个项目做出其他是-否决定，例如“该项目是英语单词”、“该项目在数据库中吗？” , "该项目属于此类别吗？" 等等

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

哈希映射：

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

Vector 和 Hashtable 是同步的，因此速度会慢一些，如果需要同步，请使用 Collections.synchronizedCollection()。选中此以获取已排序的集合。希望这有所帮助。

Answer 9

嗯，这取决于你需要什么。一般指导方针是：

List是一个集合，其中数据按插入顺序保存，每个元素都有索引。

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

Map您可以通过键访问和写入数据元素，键可以是任何可能的对象。

署名：https ://stackoverflow.com/a/21974362/2811258

有关 Java 集合的更多信息，请查看这篇文章。

Answer 10

我发现 Bruce Eckel 的 Thinking in Java 非常有帮助。他很好地比较了不同的收藏品。我曾经保留他发布的图表，显示我的立方体墙上的继承heirachy，作为快速参考。我建议你做的一件事是记住线程安全。性能通常意味着不是线程安全的。

Answer 11

用于Map键值对

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

例如，跟踪哪个人正在报道周末的哪一天。所以我们想将一个DayOfWeek对象映射到一个Employee对象。

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

在选择其中一种Map实现方式时，需要考虑几个方面。其中包括：并发性、对键和/或值中的 NULL 值的容差、迭代键时的顺序、通过引用与内容进行跟踪以及文字语法的便利性。

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