記事のタイトルは次のようにします。「Java コレクション実装の大きな時間の複雑さは何ですか?」
- Linda Hamiltonオリジナル
- 2024-10-28 02:33:31765ブラウズ
Java コレクション フレームワークの実装: 大まかな概要
「Java 短期集中コース」を教える場合、次の点に注意することが重要です。さまざまなコレクションの実装に関連する Big-O の時間の複雑さ。聴衆は Big-O 表記法には精通しているかもしれませんが、特定のコレクションに対するさまざまな操作の具体的な複雑さについては理解している可能性は低いです。
幸いなことに、書籍「Java Generics and Collections」は、これらの複雑さについての貴重な洞察を提供します。 。この記事では、書籍の情報を要約し、コレクションの各タイプ (リスト、セット、マップ、キュー) の詳細な表を示します。
リストの実装:
| Operation | ArrayList | LinkedList | CopyOnWriteArrayList |
|---|---|---|---|
| get | O(1) | O(n) | O(1) |
| add | O(1) | O(1) | O(n) |
| contains | O(n) | O(n) | O(n) |
| next | O(1) | O(1) | O(1) |
| remove(0) | O(n) | O(1) | O(n) |
| iterator.remove | O(n) | O(1) | O(n) |
セットの実装:
| Operation | HashSet | LinkedHashSet | CopyOnWriteArraySet | EnumSet | TreeSet | ConcurrentSkipListSet |
|---|---|---|---|---|---|---|
| add | O(1) | O(1) | O(n) | O(1) | O(log n) | O(log n) |
| contains | O(1) | O(1) | O(n) | O(1) | O(log n) | O(log n) |
| next | O(h/n) | O(1) | O(1) | O(1) | O(log n) | O(1) |
| Notes | h is the table capacity |
マップの実装:
| Operation | HashMap | LinkedHashMap | IdentityHashMap | EnumMap | TreeMap | ConcurrentHashMap | ConcurrentSkipListMap |
|---|---|---|---|---|---|---|---|
| get | O(1) | O(1) | O(1) | O(1) | O(log n) | O(1) | O(log n) |
| containsKey | O(1) | O(1) | O(1) | O(1) | O(log n) | O(1) | O(log n) |
| next | O(h/n) | O(1) | O(h/n) | O(1) | O(log n) | O(h/n) | O(1) |
| Notes | h is the table capacity |
キューの実装:
| Operation | PriorityQueue | ConcurrentLinkedQueue | ArrayBlockingQueue | LinkedBlockingQueue | PriorityBlockingQueue | DelayQueue | LinkedList | ArrayDeque | LinkedBlockingDeque |
|---|---|---|---|---|---|---|---|---|---|
| offer | O(log n) | O(1) | O(1) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(1) |
| peek | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) |
| poll | O(log n) | O(1) | O(1) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(1) |
| size | O(1) | O(n) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) |
以上が記事のタイトルは次のようにします。「Java コレクション実装の大きな時間の複雑さは何ですか?」の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
関連記事
続きを見る- ビットシフトと乗算/除算: Java と .NET のパフォーマンスを心配する必要がありますか?
- jconsole の JMX リモート アクセスを有効にして JVM に接続する方法
- IntelliJ IDEA で class.getResource() が Null を返すのはなぜですか?
- 以下に、質問形式を組み込んだタイトルのオプションをいくつか示します。 * Java はメモリの割り当て解除をどのように管理しますか? (率直かつ直接的) * オブジェクトを Null に設定すると、メモリの割り当て解除が保証されますか?
- 以下に、記事の内容に沿った質問ベースのタイトルをいくつか示します。 * Java コードをプロファイリングする必要がありますか? 無料で強力なツール、VisualVM をご紹介します。 * オープンソース Java プロファイリングをお探しですか? ヴィ