Java 初心者必見の Java コレクションのチートシート

可能な限り短い時間で、すべてのコレクションと同時コレクションの特性、実装方法、パフォーマンスを確認します。 「Java に精通している」ことにあまり自信がない人が読むのに適しています。

List

ArrayList

配列として実装されます。スペースを節約できますが、アレイには容量制限があります。制限を超えると、容量が 50% 増加され、System.arraycopy() を使用して新しい配列にコピーされるため、配列サイズの見積もりを提示することが最善です。デフォルトでは、要素が初めて挿入されるときにサイズ 10 の配列が作成されます。

配列subscript-get(i)/set(i,e)による要素へのアクセスはパフォーマンスが高く、これが配列の基本的な利点です。

配列の末尾に直接要素を追加する -- add(e) はパフォーマンスが高いですが、添字を押して要素を挿入または削除する場合 -- add(i,e)、remove(i)、remove(e)影響を受ける要素の一部を移動するには System.arraycopy() を使用する必要があり、パフォーマンスが低下するという基本的な欠点があります。

LinkedList

は双方向リンクリストとして実装されています。リンク リストには容量制限はありませんが、二重リンク リスト自体はより多くのスペースを使用し、追加のリンク リスト ポインター操作が必要になります。

添字による要素へのアクセス -- get(i)/set(i,e) は、悲劇的にリンクされたリストを走査してポインタを所定の位置に移動します (i>配列のサイズの半分の場合、ポインタは末尾から移動されます) 。

要素を挿入または削除するときは、前後のノードのポインタを変更するだけで済みますが、添字の両端の操作のみ、リンクされたリストのポインタの一部をたどる必要があります。ポインターの移動を保存するには、linked list-add()、addFirst()、removeLast()、または iterator() の Remove() を使用します。

CopyOnWriteArrayList

同時実行性が最適化された ArrayList。 CopyOnWrite 戦略を使用すると、まずスナップショットをコピーして変更し、次に内部ポインタが変更後の新しい配列を指すようにします。

スナップショットへの変更は読み取り操作には表示されないため、レプリケーションのコストが高くつくことに加えて、書き込みロックのみが存在し、書き込みが少なくなるシナリオに適しています。更新頻度が高い場合、または配列が大きい場合は、Collections.synchronizedList(list) を使用し、すべての操作に同じロックを使用してスレッドの安全性を確保することをお勧めします。

配列を走査して要素が既に存在するかどうかを確認する addIfAbsent(e) メソッドを追加しました。ご想像のとおり、パフォーマンスはあまり良くありません。

補足

どの実装を実装しても、contains(e)、indexOf(e)、remove(e)などの値で添え字を返すには、比較のためにすべての要素を走査する必要があり、パフォーマンスは想像どおりあまり良くありません。 。

要素の値でソートされたSortedListはなく、スレッドセーフクラスにはロックフリーのConcurrentLinkedListもありません。SetとQueueで同等のクラスを使用すると、List固有のメソッドがいくつか欠落します。

Map

HashMap

Entry[]配列で実装されたハッシュバケット配列、Keyのハッシュ値を使用してバケット配列のサイズを剰余して配列の添字を取得します。

要素を挿入するときに、2 つのキーが同じバケットに属する場合 (たとえば、ハッシュ値 1 と 17 がどちらもモジュロ 16 以降の最初のハッシュ バケットに属している場合)、Entry は次の属性を使用して、複数の Entries を 1 つのエントリに実装します。ウェイ リンク リスト ストレージでは、バケット内に後から入力されたエントリは、バケット内の現在のエントリの隣を指します。

ハッシュ値 17 のキーを探す場合は、まず最初のハッシュ バケットを見つけ、次にリンク リストを使用してバケット内のすべての要素を走査し、それらのキー値を 1 つずつ比較します。

エントリの数がバケットの数の 75% に達すると (多くの記事では、使用されたバケットの数が 75% に達したと書かれていますが、コードに基づくとそうではありません)、バケット配列は指数関数的に拡張され、すべての元のエントリが再割り当てされるため、これを見積もるのが最も適切です。

法を取得するにはビット単位の演算（hash & (arrayLength-1)）を使用した方が速いため、配列のサイズは17などの初期値を任意に与えると常に2のN乗になります。の場合は 32 に変換されます。要素を最初に配置するときのデフォルトの初期値は 16 です。

ハッシュバケット配列を走査するために iterator() が使用されると、順序が狂っているようです。

JDK8では、デフォルト値8の新しいしきい値が追加され、バケット内のエントリがしきい値を超えると、Keyを高速化するために、一方向リンクリストとしてではなく、赤黒ツリーとして保存されます。検索。

LinkedHashMap

HashMapを拡張して、最もメモリを消費するデータ構造として知られる双方向リンクリストの実装を追加します。 iterator() がサポートされている場合、エントリは挿入順序に従って並べ替えられます (ただし、更新はカウントされません。accessOrder 属性が true に設定されている場合、すべての読み取りおよび書き込みアクセスがカウントされます)。

実装はEntryへのポインタの前後に属性を追加し、挿入時にHeader Entryの前に自身を追加するというものです。すべての読み取りおよび書き込みアクセスを並べ替える必要がある場合は、前後のエントリの前後を結合して、リンクされたリスト内のエントリ自体を削除する必要があります。

ツリーマップ

スペースの制限があるため、詳細については、赤黒ツリーを使用して実装されています。 iterator() がサポートされている場合、ソートは Key 値によって行われ、Comparable インターフェースを実装する Key の昇順でソートすることも、受信 Comparator によって制御することもできます。ツリー内の要素の挿入/削除のコストは、HashMap のコストよりも大きくなることが考えられます。

最大および最小のキーを取得するfirstKey()、lastKey()、またはMapの特定のセグメントを切り取るsub(fromKey, toKey)、tailMap(fromKey)などのSortedMapインターフェースをサポートします。

ConcurrentHashMap

同時最適化されたHashMapにはデフォルトで16個の書き込みロックがあり（さらに多く設定可能）、これによりブロックの確率が効果的に分散され、読み取りロックがありません。

データ構造はSegment[]で、Segmentの中にハッシュバケット配列があり、各Segmentがロックを持っています。キーは最初にそれがどのセグメントにあるかを計算し、次にそれがどのハッシュ バケットにあるかを計算します。

putIfAbsent(key, value) やその逆の CAS を実装した replace(key, value) や replace(key, oldValue, newValue) などの ConcurrentMap インターフェースをサポートします。

put/remove アクションはアトミック アクション (たとえば、put は配列要素/エントリ ポインターへの代入操作) であるため、読み取りロックはなく、読み取り操作では更新アクションの中間状態が表示されません。

ConcurrentSkipListMap

JDK6 の新しい同時実行性に最適化された SortedMap は、SkipList を使用して実装されています。 SkipList は、赤黒ツリーおよび一般的な順序セット アルゴリズムに代わる簡略化されたものです。スペースの制限があるため、入門チュートリアルを参照してください。 Concurrent パッケージは、CAS ベースのロックフリー アルゴリズムをサポートしているため、これを使用しますが、赤黒ツリーには優れたロックフリー アルゴリズムがありません。

非常に特殊で、size() は気軽に調整できず、統計のために走査されます。

補足

nullに関して、TreeMapがComparatorを設定していない場合、ConcurrentHashMapの値はnullにできず、keyもnullもできません。 JDK8 では値を null にすることができます。ConcurrentSkipListMap は、すべての JDK でキーと値を null にすることはできません。

Set

Set は、ほとんどの場合 Map を使用して内部実装されます。これは、Map 内の KeySet が Set であり、値が false 値であり、すべて同じオブジェクトを使用しているためです。 Set の特性も、内部 Map 実装の特性を継承します。

HashSet: 内部的にはHashMapです。

LinkedHashSet: 内部的には LinkedHashMap です。

TreeSet: 内部的には TreeMap の SortedSet です。

ConcurrentSkipListSet: 内部的には、ConcurrentSkipListMap の同時最適化された SortedSet です。

CopyOnWriteArraySet: 内部的には、同時に最適化された CopyOnWriteArrayList の Set であり、その addIfAbsent() メソッドは要素の重複排除を実現するために使用されます。 前述したように、このメソッドのパフォーマンスは非常に平均的です。

補足: ConcurrentHashSet が欠落しているようです。内部的には ConcurrentHashMap の単純な実装があるはずですが、JDK はそれを提供していません。 Jetty はそれを独自にシールしており、Guava は java.util.Collections.newSetFromMap(new ConcurrentHashMap()) を直接使用して実装しています。

Queue

Queueは両端から入ったり出たりするListなので配列やリンクリストでも実装できます。

--Ordinary Queue--

LinkedList

はい、二重リンクリストとして実装されたLinkedListはListでありQueueでもあります。これは、null を配置できる唯一のキューです。

ArrayDeque

循環配列で実装された双方向Queue。サイズは 2 の倍数で、デフォルトは 16 です。

通常の配列は、最後に要素をすばやく追加することしかできません。FIFO をサポートし、配列の先頭から要素をすばやく削除するには、ループ配列を使用する必要があります。先頭と末尾に 2 つの添え字があります。ポップアウトされると、先頭の添字がインクリメントされます。配列空間の終わりに達した場合、要素はループ内で配列 [0] に割り当てられます (この時点で先頭の添字が 0 より大きい場合)。 、チームの先頭が要素を飛び出して空きがあることを意味します)、チームの末尾の添字は 0 を指します。次に、次の要素を挿入して配列 [1] に割り当てます。下付き文字は 1 を指します。キューの末尾の添字がキューの先頭に追いついた場合、配列内のすべてのスペースが使い果たされたことを意味し、配列は 2 倍になります。

PriorityQueue

バイナリヒープを使用して実装された優先キュー。詳細は入門チュートリアルを参照してください。FIFOではなくなり、要素によって実装されたComparableインターフェイス、またはComparatorに渡された比較結果に基づいてデキューされます。 、値が大きいほど優先度が高くなります。ただし、 iterator() の戻り値はソートされないことに注意してください。

--スレッドセーフキュー--

ConcurrentLinkedQueue/ConcurrentLinkedDeque

無制限の同時実行に最適化されたキューは、リンクされたリストに基づいて、CAS に依存するロックフリーのアルゴリズムを実装します。

ConcurrentLinkedQueue の構造は、一方向のリンクされたリストと、先頭/末尾の 2 つのポインタです。キューに参加するときに、キューの末尾要素の次のポインタを変更し、末尾が新たに指すように変更する必要があるためです。結合要素。2 つの CAS アクションはアトミックにできないため、スペースの制限により特別なアルゴリズムが必要です。詳細については、入門チュートリアルを参照してください。

PriorityBlockingQueue

無制限の同時実行性が最適化されたPriorityQueueもバイナリヒープに基づいています。パブリック読み取り/書き込みロックを使用します。 BlockingQueue インターフェイスは実装されていますが、ブロッキング キューの特性はありません。スペースが不足すると自動的に拡張されます。

DelayQueue

内部にPriorityQueueが含まれており、これも無制限です。この要素は Delayed インターフェイスを実装する必要があり、呼び出されるたびに、トリガー時間までの時間を返す必要があります。それが 0 未満の場合は、トリガーの時間であることを意味します。
pull() のとき、peek() を使用してキューの先頭の要素をチェックし、トリガー時間に達したかどうかを確認します。 ScheduledThreadPoolExecutor も同様の構造を使用します。

--スレッドセーフなブロッキングキュー--

BlockingQueueのキューの長さは、プロデューサーとコンシューマーの速度が大きく異なりすぎず、メモリの枯渇を避けるために制限されています。キューの長さは、設定後に変更することはできません。キューに入るときにキューがいっぱいである場合、またはキューから出るときにキューが空である場合、さまざまな関数の影響を以下の表に示します。

例外を報告する場合があります。 ブール値を返します。 待機をブロックする場合があります。 待機時間を設定できます。

キューに入る Add(e) Offer( e) put(e) Offer(e, timeout, Unit)

dequeue Remove() Paul() take() Paul(timeout, Unit)

View element() Peak () none none

ArrayBlockingQueue

修正 Long 同時実行に最適化された BlockingQueue、ループ配列に基づいて実装されました。キューがいっぱいまたは空の場合のブロック状態を管理するための、共通の読み取り/書き込みロックと、notFull と notEmpty の 2 つの条件があります。

LinkedBlockingQueue/LinkedBlockingDeque

リンクされたリストに基づく、同時実行性に最適化された長い BlockingQueue を選択できるため、長さを Integer.MAX_VALUE に設定できます。リンクリストの特性を活かし、takeLockとputLockの2つのロックを分離し、notEmptyとnotFullを使用してキューが満杯または空の場合のブロッキング状態を管理し続けます。

補足

JDK7 には LinkedTransferQueue があり、Producer によって入力された要素が Consumer によって確実に取得されて返されるようにするため、時間があるときに学習するとよいでしょう。