选择 Java Collection 实现的经验法则？

StackOverflow https://stackoverflow.com/questions/48442

  •  09-06-2019
  •  | 
  •  

题

在 Java Collection 接口（如 List、Map 或 Set）的不同实现之间进行选择时，有人有一个好的经验法则吗？

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

有帮助吗？

解决方案

我总是根据具体情况做出这些决定，具体取决于用例，例如：

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

然后我拿出了我方便的第五版 Java 简介 并比较大约 20 个选项。第五章中有一些漂亮的小表格，可以帮助人们弄清楚什么是合适的。

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

其他提示

我真的很喜欢 Sergiy Kovalchuk 的这份备忘单 博客条目:

Java Map/Collection Cheat Sheet

更详细的是 Alexander Zagniotov 的流程图，但不幸的是它已离线。

我假设您从上面的答案中知道列表、集合和映射之间的区别。为什么要在它们的实现类之间进行选择是另一回事。例如：

列表:

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

放：

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

地图： HashMap 和 TreeMap 的性能和行为与 Set 实现并行。

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

理论上是有用的 大哦 权衡，但实际上这些几乎无关紧要。

在现实世界的基准测试中， ArrayList 表现优于 LinkedList 即使有大清单和“前部附近的许多插入”之类的操作。学术界忽略了这样一个事实，即实际算法具有恒定的因素会淹没渐近曲线。例如，链表需要为每个节点进行额外的对象分配，这意味着创建节点的速度较慢，内存访问特性也较差。

我的规则是：

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

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

List、Map 和 Set 有不同的用途。我建议阅读有关 Java Collections Framework 的内容： http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html.

更具体一点：

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

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

Vector和ArrayList的主要区别在于前者是同步的，后者不是同步的。您可以阅读有关同步的更多信息 Java 并发实践.

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

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

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

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

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

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

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

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

对于具体的实现，映射和集合存在保序变体，但很大程度上取决于速度。我倾向于将 ArrayList 用于相当小的列表，将 HashSet 用于相当小的集合，但是有很多实现（包括您自己编写的任何实现）。HashMap 对于地图来说非常常见。任何超过“相当小的”的东西，你都必须开始担心内存，这样在算法上就会更加具体。

这一页 有 地段 动画图像以及测试 LinkedList 与 LinkedList 的示例代码如果您对硬数字感兴趣，请使用 ArrayList。

编辑： 我希望以下链接展示了这些东西实际上只是工具箱中的物品，您只需考虑您的需求是什么：请参阅 Commons-Collections 版本 地图, 列表 和 放.

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

数组列表：

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

链表：

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

哈希集：

  • 对某个项目做出其他是非决定，例如“项目是英语单词”，“数据库中的项目是吗？” ，“此类别中的项目吗？” ETC。

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

哈希映射：

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

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

我发现 Bruce Eckel 的《Java 思维》非常有帮助。他很好地比较了不同的收藏。我曾经在我的立方体墙上保留了他发布的显示继承层次结构的图表，作为快速参考。我建议您做的一件事是牢记线程安全。性能通常意味着线程不安全。

嗯，这取决于你需要什么。一般准则是：

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

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

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

enter image description here归因： https://stackoverflow.com/a/21974362/2811258

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top