宝物: データ構造 - 配列リスト

前書き

デフォルトのサイズ

デフォルトのサイズは10

増設は元のキャパの半分で、1回増設したら15回。

遅延ロード

1.7以降の初期化遅延

つまり、要素が追加されるまで実際の容量は割り当てられません。

パラメータなしのコンストラクタは、Object 配列のデフォルトサイズを指定します。 パラメータなしのコンストラクタは、容量 10 の Object 配列を直接作成するのではなく、遅延ロード戦略を採用していることに注意してください。オブジェクト配列

最初の要素が配列に追加されると、DEFAULTCAPACITY_EMPTY_ELEMENTDATAは、配列をどれだけ拡張するかを知ることができます。

内部構造

ArrayListの内部構造で、Object[]型の配列です。

コンストラクタ

• ArrayList(int initialCapacity)

コンストラクタ：指定された容量値を受け取り、作成される配列を初期化することを示します。

• ArrayList()

コンストラクタ：デフォルトのコンストラクタで、空の配列を作成します。

• ArrayList(Collection<? extends E> c)

コンストラクタ：Collection エンティティを受け取り、Collection エンティティを ArrayList オブジェクトに変換します。

failFast

• ArrayListはシングルスレッド環境でのみ使用できます。マルチスレッド環境では同時実行安全性の問題が発生します。

• modCountは主にArrayListの変更回数を記録するために使用されます。もしmodCountの変更中にスレッド操作があった場合、つまり現在のArrayListを同時に複数のスレッドが変更した場合、"ConcurrentModificationException "がスローされます。thisfailFastメカニズム」とも呼ばれます。

• HashMap、LinkedListなど、多くのスレッドセーフでないクラスにはfailFastメカニズムがあります。

• つまり、あるスレッドがコンテナを反復処理するときに、他のスレッドがコンテナ内の要素を変更すると、反復処理しているスレッドは "ConcurrentModificationException" をスローします。

Javaのコレクション・クラスで作業する場合、ConcurrentModificationExceptionが発生すると、フェイルファスト関連の状況が優先されます。によって行われたのではないある変更があったことを発見すると、例外がスローされます。

双方向リスト

• 双方向リストの実装の基礎となるLinkedListは、Nodeオブジェクトを構築するために新しい要素を追加するときに、単に新しいNodeに次のNodeを割り当てることができますので、。

• LinkedListは、ArrayListの展開を伴わないため、ArrayListよりも効率的に要素を挿入することができます。しかし、このデータ構造のため、ランダムアクセスができません。

スレッドの安全性を確保する方法

1.スレッドセーフメソッド

List list = Collections.synchronizedList(new ArrayList<>；

Collectionsは、リストが同期的でスレッドセーフであることを保証するメソッドsynchronizedListを提供します。

2、CopyOnWriteArrayList：コピーオンライト

• CopyOnWriteコンテナは、書き込み時にコピーのコンテナは、コンテナに要素を追加するには、現在のコンテナObject[] addに直接ではなく、最初の現在のコンテナObject[] Copyは、新しいコンテナObject[] newElementsをコピーし、新しいコンテナに要素を追加しますObject[] newElement内部。newElement、次に新しいコンテナに要素を追加 Object[]、要素を追加、次に新しいコンテナへの元のコンテナ参照、setArray(newElements )；

• この利点は、現在のコンテナに要素が追加されないため、ロックの必要なくCopyOnWriterコンテナに対して同時読み込みができることです。したがって、CopyOnWriteコンテナも、読み込みと書き込みに別のコンテナを使用する、読み書き分離のアイデアです。

ヌル値を許可するかどうか

ヌル値と重複要素の許可

時間の複雑さ

基本的な実装は配列に基づいているため、O(1)の複雑さでランダム検索を実行することが保証されています。

static変更されたEMPTY_ELEMENTDATAおよびDEFAULTCAPACITY_EMPTY_ELEMENTDATA

addメソッドの一般的な流れ

最初の要素が追加されるとき、minCapacityは1です。

Math.max()メソッドの比較後、minCapacityは10になります。

そして、secureExplicitCapacityの呼び出しの直後にmodCountの値を更新します。

そして容量拡張が必要かどうかの判断

oldCapacity は古い配列の容量です。

newCapacity は新しい配列の容量です。

新しい容量のサイズが必要最小容量より小さいかどうかをチェックし、小さい場合は最小容量をアレイの新しい容量として設定します。

新しい容量がMAX_ARRAY_SIZEより大きい場合は、giantCapacityを使用して2つを比較します。

hugeCapacity ロジック：

minCapacityとMAX_ARRAY_SIZEを比較してください。

minCapacityが大きい場合、新しい配列のサイズとしてInteger.MAX_VALUEを使用します。

MAX_ARRAY_SIZEが大きい場合、MAX_ARRAY_SIZEを新しい配列のサイズとして使用します。

MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

追加メソッド実行フローの概要

• これはaddメソッドの最初の呼び出しで、拡張値の容量が10になった後です。

• 続けて2番目の要素を追加します。

• secureCapacityInternalメソッドでは、elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATAが保持されないため、secureExplicitCapacityメソッドが直接実行されます。

• さらに3、4......10個の要素を追加するとします。10個の要素

• 11番目の要素を追加するとき、それはnewCapacityがminCapacityよりも大きい15であると計算されたときにgrowメソッドに入りますが、判定が保持されない場合は、最初の。newCapacityが配列の最大サイズより大きくない場合は、giantCapacityメソッドには入りません。配列の容量は15に拡張され、addメソッドでtrueを返し、サイズが11に増加します。

add(int index,E element)

add(intインデックス, E要素)メソッドのinserts)はおおよそ次のようになります。

• 配列に十分なスペースがあるかどうかを検出

• インデックスとそれに続くすべての要素を1つ後ろに移動します。

• インデックスに新しい要素を挿入します。

• シーケンスの指定された位置に新しい要素を挿入するには、その位置以降にあるすべての要素を1つ戻して、新しい要素のためのスペースを確保する必要があります。この操作の時間複雑度はO(N)であり、要素を頻繁に移動させると、特に集合の要素数が大きい場合に効率性の問題が発生する可能性があります。

• 日常的な開発では、大規模なコレクションで2番目の挿入メソッドを呼び出す必要がない場合は、呼び出さないようにする必要があります。

ArrayListこれはjdk 1.7から利用できるようになったremoveメソッドです。

remove(int index) 添え字による削除

nteger.MAX_VALUE - 8

主に考慮異なるJVMに取って、いくつかのJVMは、いくつかのデータヘッダに追加され、拡張容量がMAX_ARRAY_SIZEよりも大きい場合、それは唯一のInteger.MAX_VALUEに取ることができるよりも大きい場合は、比較を行うために最小必要な容量とMAX_ARRAY_SIZEを比較しに行きますが、それ以外の場合はInteger.MAX_VALUE -8です。これは jdk1.7 以降の話です。

https://..///.ml