不同 Java 集合框架操作的 Big-O 时间复杂度是多少？

Java 集合框架实现的 Big-O 表示法

在即将到来的 Java 速成课程中，有必要提供一个简洁的不同集合实现上的各种操作的时间复杂度的总结。

列表实现

Implementation	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)

集合实现

Implementation	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)	-

地图实现

Implementation	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)	-

队列实现

Implementation	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 集合框架操作的 Big-O 时间复杂度是多少？的详细内容。更多信息请关注PHP中文网其他相关文章！