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

我很快就会教"Java崩溃课程".虽然假设观众成员会知道Big-O表示法可能是安全的,但假设他们知道各种集合实现的各种操作的顺序是什么可能是不安全的.

我可以花时间自己生成一个摘要矩阵,但如果它已经在公共领域的某个地方出现,我肯定想重复使用它(当然还有适当的信用.)

任何人有任何指针？

1> toolkit..：

---

Java Generics和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)

设置实现:

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

集合概述有一个很好的汇总表.

带注释的大纲列出了一个页面上的所有实现.

---

您必须指定这些数字的情况,例如,如果删除数组中间或末尾的元素,则从Arraylist中删除可能需要O(n).

2> Ben J..：

---

这个网站非常好,但不是特定于Java:http://bigocheatsheet.com/

---

这就是我们不使用URL作为答案的原因.据我所知,该文件/服务器已不再可用!

3> matt b..：

---

来自Sun的Javadocs每个集合类通常会告诉你你想要什么.HashMap,例如:

假设散列函数在桶之间正确地分散元素,该实现为基本操作(get和put)提供了恒定时间性能.对集合视图的迭代需要与HashMap实例的"容量"(桶的数量)加上其大小(键 - 值映射的数量)成比例的时间.

TreeMap:

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

树集:

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

(强调我的)

---

如果您阅读上面的引用,它表示它是恒定时间"假设散列函数在桶之间正确地分散元素".根据CS理论,当散列函数"好"(平均发生)时,散列表具有恒定时间操作,但在最坏的情况下可能需要线性时间.

---

@Overflown - 从技术上讲,obj.equals()从复杂性的角度来看并不重要,因为它只是与集合中项目数量相关的"常量"的一部分.

4> newacct..：

---

上面的人给出了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)