☰

Java Collections Framework 実装の Big-O 要約? [closed] 質問する

tag-icon • tag-icon java collections big-o
Java Collections Framework 実装の Big-O 要約? [closed] 質問する

近々、「Java 短期集中講座」を開講する予定です。受講生が Big-O 記法を知っていると想定するのはおそらく安全ですが、さまざまなコレクション実装でのさまざまな操作の順序を知っていると想定するのは安全ではないでしょう。

時間をかけて要約マトリックスを自分で生成することもできますが、それがすでにどこかのパブリック ドメインに公開されている場合は、ぜひそれを再利用したいと思います (もちろん、適切なクレジットを付けて)。

誰か何かアドバイスはありますか?

ベストアンサー1

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

Javadocの下部にはjava.utilパッケージにはいくつかの良いリンクが含まれています:

おすすめ記事