为了账号安全,请及时绑定邮箱和手机立即绑定

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

/ 猿问

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

拉风的咖菲猫 2019-08-14 17:12:36

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

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

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

任何人有任何指针?


查看完整描述

3 回答

?
慕容森

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

查看完整回答
反对 回复 2019-08-14
?
冉冉说

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


查看完整回答
反对 回复 2019-08-14
?
繁星coding

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

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

TreeMap

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

树集

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


查看完整回答
反对 回复 2019-08-14

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信