Java初心者のための重要なチートシート

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

List

ArrayList

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

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

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

LinkedList

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

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

要素を挿入または削除するときは、前と次のノードのポインターを変更するだけで済みますが、添字の両端の操作のみでリンク リスト ポインターの一部をトラバースする必要があります。リンクされたリスト – 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 の後の最初のハッシュ バケットに属します)、エントリは次の属性を使用して、複数のエントリを 1 つのエントリに実装します。ウェイ リンク リスト ストレージでは、バケット内に後から入力されたエントリは、バケット内の現在のエントリの隣を指します。

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

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

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

Iterator() はハッシュ バケット配列に沿って走査しますが、順序が狂っているようです。

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

LinkedHashMap

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

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

TreeMap

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

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

ConcurrentHashMap

同時実行に最適化された HashMap には、デフォルトで 16 個の書き込みロックがあり (さらに多くの値を設定可能)、これによりブロックの可能性が効果的に分散され、読み取りロックがありません。
データ構造は Segment[] で、Segment 内にはハッシュバケット配列があり、各 Segment にはロックがあります。キーは最初にそれがどのセグメントにあるかを計算し、次にそれがどのハッシュ バケットにあるかを計算します。

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

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

ConcurrentSkipListMap

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

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

補足

null に関して、TreeMap が Comparator を設定しない場合、ConcurrentHashMap の値は 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 のセットです。その addIfAbsent() メソッドは、要素の重複排除を実現するために使用されます。前述したように、このメソッドのパフォーマンスは非常に平均的です。
追記: ConcurrentHashSet が欠落しているようです。内部的には ConcurrentHashMap の単純な実装があるはずですが、JDK はそれを提供していません。 Jetty はそれを独自にシールしており、Guava は java.util.Collections.newSetFromMap(new ConcurrentHashMap()) を直接使用して実装しています。

Queue

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

– 通常のキュー –

LinkedList

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

ArrayDeque

円形配列で実装された双方向キュー。サイズは 2 の倍数で、デフォルトは 16 です。

通常の配列は最後に要素をすばやく追加することしかできません。FIFO をサポートし、配列の先頭から要素をすばやく削除するには、ループ配列を使用する必要があります。先頭と末尾に 2 つの添え字があります。ポップされると、先頭の添字がインクリメントされます。配列空間の終わりに達した場合、要素は循環的に配列 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 のキューの長さは、プロデューサーとコンシューマーの速度が大きく異なりすぎず、メモリの枯渇を避けるために制限されています。キューの長さは、設定後に変更することはできません。キューに入るときにキューがいっぱいである場合、またはキューから出るときにキューが空である場合の、さまざまな関数の影響を以下の表に示します。円形配列。キューがいっぱいまたは空の場合のブロック状態を管理するための、共通の読み取り/書き込みロックと、notFull と notEmpty の 2 つの条件があります。

LinkedBlockingQueue/LinkedBlockingDeque

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

補足

JDK7 には LinkedTransferQueue があります。transfer(e) メソッドは、プロデューサーによって入力された要素がコンシューマーによって取得されて返されることを保証します。時間があるときに学習してください。