Java Collections Framework 实现的 Big-O 摘要？

Big-O summary for Java Collections Framework implementations?

提问by Jared

I may be teaching a "Java crash-course" soon. While it is probably safe to assume that the audience members will know Big-O notation, it is probably not safe to assume that they will know what the order of the various operations on various collection implementations is.

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

I could take time to generate a summary matrix myself, but if it's already out there in the public domain somewhere, I'd sure like to reuse it (with proper credit, of course.)

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

Anyone have any pointers?

有人有任何指示吗？

采纳答案by Ben J

This website is pretty good but not specific to Java: http://bigocheatsheet.com/

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

回答by matt b

The Javadocs from Sun for each collection class will generally tell you exactly what you want. HashMap, for example:

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

This implementation provides constant-time performancefor the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance(the number of buckets) plus its size (the number of key-value mappings).

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

TreeMap:

树图：

This implementation provides guaranteed log(n) time costfor the containsKey, get, put and remove operations.

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

TreeSet:

树集：

This implementation provides guaranteed log(n) time cost for the basic operations(add, remove and contains).

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

(emphasis mine)

（强调我的）

回答by toolkit

The book Java Generics and Collectionshas this information (pages: 188, 211, 222, 240).

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

List implementations:

列出实现：

                      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 implementations:

设置实现：

                      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 implementations:

地图实现：

                      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)

Queue implementations:

队列实现：

                      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)

The bottom of the javadoc for the java.utilpackage contains some good links:

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

• Collections Overviewhas a nice summary table.
• Annotated Outlinelists all of the implementations on one page.

• Collections Overview有一个很好的汇总表。
• Annotated Outline在一页上列出了所有的实现。

回答by newacct

The guy above gave comparison for HashMap / HashSet vs. TreeMap / TreeSet.

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

I will talk about ArrayList vs. LinkedList:

我将讨论 ArrayList 与 LinkedList：

ArrayList:

数组列表：

• O(1) get()
• amortized O(1) add()
• if you insert or delete an element in the middle using ListIterator.add()or Iterator.remove(), it will be O(n) to shift all the following elements

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

LinkedList:

链表：

• O(n) get()
• O(1) add()
• if you insert or delete an element in the middle using ListIterator.add()or Iterator.remove(), it will be O(1)

• 在） get()
• O(1) add()
• 如果使用ListIterator.add()or在中间插入或删除元素，则为Iterator.remove()O(1)