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

Question

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

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

有人有指针吗？

Answer 1

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

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

有人有指针吗？列出实现：

                      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)