Java集合框架实现的Big-O摘要？
我可能很快会教授一个“Java崩溃课程”。 虽然假定观众成员可能知道Big-O符号可能是安全的，但假定他们知道各种集合实现上的各种操作的顺序可能是不安全的。
我可以花时间自己创build一个总结matrix，但是如果它已经在公共领域的某个地方，我肯定会重用它（当然，要有适当的信用）。
任何人有任何指针？
这个网站相当不错，但并不特定于Java： http : //bigocheatsheet.com/
这本书的Javagenerics和集合有这个信息（页：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的底部包含一些很好的链接：
- 集合概述有一个很好的汇总表。
- 带注释的大纲列出了一个页面上的所有实现。
来自Sun的Javadocs通常会告诉你你想要什么。 HashMap ，例如：
这个实现为基本操作（get和put）提供了恒定的性能 ，假设散列函数在桶之间正确分散元素。 对集合视图的迭代需要的时间与HashMap实例的“容量” （桶的数量）加上其大小（键值映射的数量） 成正比 。
TreeMap ：
这个实现为containsKey，get，put和remove操作提供了保证的log（n）时间成本 。
TreeSet ：
这个实现为基本操作 （添加，移除和包含）提供了保证的log（n）时间成本 。
（重点是我的）
上面的家伙比较了HashMap / HashSet与TreeMap / TreeSet。
我将讨论ArrayList与LinkedList：
ArrayList的：
- O（1）get（）
- 摊销O（1）add（）
- 如果使用ListIterator.add（）或Iterator.remove（）在中间插入或删除元素，则将O（n）移动所有后续元素
链表：
- O（n）get（）
- O（1）add（）
- 如果使用ListIterator.add（）或Iterator.remove（）在中间插入或删除元素，则将为O（1）
