さまざまな Java コレクション フレームワーク操作の大きな時間の複雑さは何ですか?

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)

追加リソース

さらに詳しく調べるには、次の貴重なリソースを検討してください。

• コレクションの概要: 役立つ概要表を提供します
• 注釈付きの概要: 実装の包括的なリストが 1 ページに含まれています

以上がさまざまな Java コレクション フレームワーク操作の大きな時間の複雑さは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。