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

Question

任何人都有一个很好的经验法则,可以在列表,地图或集合等Java Collection接口的不同实现之间进行选择？

例如,一般为什么或在什么情况下我更喜欢使用Vector或ArrayList,Hashtable或HashMap？

Answer 1

我真的很喜欢Sergiy Kovalchuk 博客文章中的这个备忘单:

更详细的是Alexander Zagniotov的流程图,但不幸的是它处于脱机状态.

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

我总是根据具体情况逐个做出决定,例如:

• 我需要订购吗？
• 我有空键/值吗？DUPS？
• 是否会被多个线程访问
• 我需要一个键/值对吗？
• 我需要随机访问吗？

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

好吧,也许如果我知道一个简单的ArrayList或HashSet将会完成这个技巧,我将不会看到它.;)但如果有关于我的使用的东西很复杂,你打赌我在书中.顺便说一句,我虽然Vector应该是'老帽' - 我已经好几年没用了.

Answer 4

从理论上讲,有一些有用的Big-Oh权衡,但在实践中这几乎无关紧要.

在现实世界的基准测试中,即使使用大型列表以及"前端附近有大量插入"等操作也能ArrayList表现出色LinkedList.学术界忽略了这样一个事实,即真实算法具有可以压倒渐近曲线的常数因子.例如,链接列表需要为每个节点分配额外的对象,这意味着创建节点的速度较慢,而内存访问特性则要差得多.

我的规则是:

1. 始终从ArrayList和HashSet和HashMap开始(即不是LinkedList或TreeMap).
2. 类型声明应该始终是一个接口(即List,Set,Map),因此,如果探查器或代码审查证明,您可以更改实现而不会破坏任何内容.

Answer 5

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

列表,地图和集合用于不同的目的.我建议您阅读http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html上的Java Collections Framework .

更具体一点:

• 如果需要类似数组的数据结构,则需要使用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,哈希变体将比树/排序更快.Hash algortihms倾向于具有O(1)性能,而树将是O(log n).