61

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

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

4

11 回答 11

96

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

Java Map/Collection 备忘单

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

Alexander Zaniotov 选择 Collection 实现的流程图

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

于 2013-07-02T08:19:11.410 回答
24

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

清单

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

放:

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

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

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

于 2008-09-07T14:17:46.243 回答
16

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

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

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

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

于 2008-09-07T14:03:48.913 回答
12

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

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

我的规则是:

  1. 总是从 ArrayList 和 HashSet 和 HashMap 开始(即不是 LinkedList 或 TreeMap)。
  2. 类型声明应该始终是一个接口(即 List、Set、Map),因此如果分析器或代码审查证明不是这样,您可以在不破坏任何内容的情况下更改实现。
于 2008-09-07T15:26:05.567 回答
8

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

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的区别类似,前者是同步的,后者是不同步的。

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

于 2008-09-07T14:03:48.180 回答
5

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

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

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

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

于 2008-09-07T15:18:39.530 回答
2

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

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

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

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

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

于 2008-09-07T14:06:20.950 回答
2

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

数组列表:

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

链表:

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

哈希集:

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

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

哈希映射:

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

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

于 2017-06-21T17:01:51.163 回答
2

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

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

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

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

在此处输入图像描述 署名:https ://stackoverflow.com/a/21974362/2811258

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

于 2019-05-30T08:04:29.180 回答
1

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

于 2008-09-07T14:30:16.637 回答
1

用于Map键值对

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

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

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

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

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

Java 11 中的地图实现表,比较它们的特性

于 2020-01-19T01:23:30.847 回答