177

我可能很快就会教授“Java 速成课程”。虽然假设观众成员会知道 Big-O 表示法可能是安全的，但假设他们会知道各种集合实现上的各种操作的顺序可能是不安全的。

我可以花时间自己生成一个汇总矩阵，但如果它已经存在于公共领域的某个地方，我肯定想重用它（当然，有适当的信用。）

有人有任何指示吗？

4

4 回答 4

262

Java 泛型和集合一书有此信息（第 188、211、222、240 页）。

列出实现：

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

设置实现：

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
EnumSet               O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

地图实现：

                      get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)   h is the table capacity 
EnumMap               O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n)    O(1)

队列实现：

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)

java.util包的 javadoc 底部包含一些很好的链接：

于 2009-02-18T04:35:20.220 回答
164

这个网站非常好，但不是特定于 Java：http ://bigocheatsheet.com/ 这是一张图片，以防此链接不起作用

于 2010-10-29T07:41:28.640 回答
13

Sun 为每个集合类提供的 Javadocs 通常会准确地告诉您您想要什么。哈希映射，例如：

此实现为基本操作（get 和 put）提供恒定时间性能，假设哈希函数将元素正确地分散在桶中。集合视图的迭代需要的时间与 HashMap 实例的“容量”（桶的数量）加上它的大小（键值映射的数量）成正比。

树图：

此实现为containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本。

树集：

此实现为基本操作（添加、删除和包含）提供有保证的 log(n) 时间成本。

（强调我的）

于 2009-02-18T04:31:55.080 回答
6

上面的人对 HashMap / HashSet 与 TreeMap / TreeSet 进行了比较。

我将讨论 ArrayList 与 LinkedList：

数组列表：

  • O(1)get()
  • 摊销 O(1)add()
  • 如果使用ListIterator.add()or在中间插入或删除一个元素Iterator.remove()，将 O(n) 移动以下所有元素

链表：

  • 在）get()
  • O(1)add()
  • 如果你在中间使用ListIterator.add()or插入或删除一个元素Iterator.remove()，它将是 O(1)
于 2009-05-02T00:52:30.650 回答