Java集合框架实现的大O总结？

Question

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

我可以花时间自己生成一个摘要矩阵，但是如果它已经存在于公共领域的某个地方，我肯定会重用它(当然，要有适当的信任)。

有谁有什么建议吗？

Answer 1

这个网站非常好，但不是专门针对Java的：http://bigocheatsheet.com/

​

Answer 2

这本书的Java Generics and Collections有这个信息(页: 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)

Set实现：

                      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)

Map实现：

                      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底部包含一些很好的链接：

• Collections Overview有一个很好的摘要，table.
• Annotated Outline在一个页面上列出了所有的实现。

Answer 3

Sun为每个集合类提供的Javadoc通常会确切地告诉您您想要什么。HashMap，例如：

此实现为基本操作(get和put)提供了constant-time performance，假设散列函数将元素适当地分散到存储桶中。在集合视图上迭代所需的时间与HashMap实例的“容量”(存储桶的数量)加上其大小(键值映射的数量)成比例。

TreeMap

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

TreeSet

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

(强调我的)