Java集合框架实施的大概要？

小开

Sun 为每个集合类提供的 Javadocs 通常会准确地告诉您需要什么:

这个实现为基本操作(get 和 put)提供了 定时性能定时性能，假设 hash 函数在桶中正确地分散元素。对集合视图的迭代需要 时间与 HashMap 实例的“容量”成正比(桶的数量)加上它的大小(键-值映射的数量)。

树木地图 :

这个实现为包含键、获取、放置和删除操作提供了 保证对数(n)时间成本。

TreeSet :

这个实现提供了 基本操作的保证日志(n)时间成本(添加、删除和包含)。

(强调我的)

小开

书 Java 泛型和集合有这些信息(页数: 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 底部包含一些好的链接:

CollectionsOverview 有一个很好的汇总表。
注释大纲在一个页面上列出了所有的实现。

小开

上面的人给出了 HashMap/HashSet 与 TreeMap/TreeSet 的比较。

我将讨论 ArrayList 和 LinkedList:

数组列表:

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

LinkedList:

O (n) get()
O (1) add()
如果您使用 ListIterator.add()或 Iterator.remove()在中间插入或删除一个元素，它将是 O (1)

小开

最佳答案

这个网站相当不错，但不是特别针对 Java 的: < a href = “ http://bigocheatsheet.com/”rel = “ norefrer”> http://bigocheatsheet.com/