Java中最快的集合是什么?
我只需要添加和删除操作,顺序不重要,相等的元素不是问题,除添加和删除之外没有其他重要内容。
无大小限制也很重要。
这些集合将包含对象。
目前我正在使用ArrayDeque,因为我发现这是最快的队列实现。
Java中最快的集合是什么?
我只需要添加和删除操作,顺序不重要,相等的元素不是问题,除添加和删除之外没有其他重要内容。
无大小限制也很重要。
这些集合将包含对象。
目前我正在使用ArrayDeque,因为我发现这是最快的队列实现。
ArrayDeque
是最好的选择。参见这个基准测试,它来自于这篇博客文章,介绍了关于这个问题的基准测试结果。相比于LinkedList
需要分配新节点的开销以及ArrayList
在删除元素时要移动数组内容的开销,ArrayDeque
没有这些额外的开销。在基准测试中,对于大队列,它的性能是LinkedList
的3倍,甚至在空队列上表现略好于ArrayList
。为了获得最佳性能,您可能需要给它一个足够大的初始容量,以便能够在每次添加元素时避免重复调整大小。
在ArrayList
和LinkedList
之间,似乎取决于队列在任何给定时间包含的平均总元素数量,并且LinkedList
在大约10个元素时就开始超过ArrayList
。
ArrayList
大致相当,尽管ArrayDeque
的javadoc表明它可能会稍微快一些。而且,鉴于问题中的要求,类似堆栈的使用也可以正常工作。不过,基准测试专门针对FIFO队列使用(您可以在链接的博客文章中看到代码示例)。 - ColinDjava.util.LinkedList
- 它是双向循环链表,因此在一端添加和在另一端取出的时间复杂度都是O(1)。Queue
接口引用它,以便在需要时轻松更改(如果当然,队列是您首先需要的)。ArrayDeque
更好的结论。两者都有O(1)操作,但LinkedList
会创建新对象(节点),这会稍微影响性能。由于两者都有O(1),我认为选择LinkedList
也不会有太大问题。ArrayDeque
是客观上更好的选择。 - ColinDArrayDeque
在作为队列或栈使用时,在添加和删除前/后端时是 O(1) 的,因为它是一个循环数组,在这些情况下不会复制任何内容。此外,重新调整大小是一种偶尔需要进行的操作,通常可以通过适当的初始容量来避免。LinkedList
每次在队列中进行添加/删除操作时都需要额外创建一个对象(以及该对象的垃圾回收)。我提供的基准测试结果表明,ArrayDeque
的速度始终比 LinkedList
快 3 倍左右。 - ColinDO(1) != O(1)
。O()
仅是复杂度的一种度量方式,而非执行时间。一个始终需要 5 年时间的操作无论 n
的大小如何都是 O(1)
,而一个始终需要 5 毫秒的操作也是 O(1)
。我宁愿使用只需 5 毫秒的操作。即使一个操作每个元素需要 5 毫秒(即 O(n)
),如果 n
不太大,它也会比需要 5 年的操作更好。 - Erick G. HagstromConcurrentLinkedDeque 是多线程队列的最佳选择。