ArrayList下位原理ソース分析

1概要
ArrayListは配列で実装されており、動的配列であり、容量が自動的に増加することができます.リスト、RandomAccess、Serializable、Cloneableなど、多くのインタフェースが実装されていることは、次のクラス宣言を参照してください.

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable

はRandomAccessインタフェースを実現する:従ってArrayListは高速ランダムアクセスをサポートし、本質的には下付きシーケンス番号によるランダムアクセス

である.

Serializableインタフェースを実現する:ArrayListにシーケンス化をサポートさせ、シーケンス化によって

を伝送する.

実装Cloneableインタフェース:ArrayListが

をクローンできるようにする.
2最下位キー

transient Object[] elementData;

ArrayListの下位層は本質的に配列であり、この配列でデータを保存するtransient:Javaキーワード、変数修飾子、transientでインスタンス変数を宣言すると、オブジェクトが格納されている場合、その値は維持されません.言い換えれば、transientキーワードでタグ付けされたメンバー変数はシーケンス化プロセスに関与しません.
Javaのserializationは、オブジェクトインスタンスを永続化するメカニズムを提供します.オブジェクトを永続化すると、特殊なオブジェクトデータメンバーが存在する可能性があります.serializationメカニズムで保存したくないです.特定のオブジェクトのドメインでserializationを閉じるには、このドメインの前にキーワードtransientを付けることができます.オブジェクトがシーケンス化されると、transient型変数の値はシーケンス化の表現に含まれないが、transient型でない変数は含まれる.
3コンストラクタ

ArrayList():初期容量0のリスト

を構築するデフォルトの構築方法

    public ArrayList() {
        //              
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

ArrayList(int initialCapacity):指定初期容量を有する空のリスト

を構築する.

  public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //          ，          initialCapacity
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
             //          ，           
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
             //       
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

ArrayList(Collection extends E> c):collectionを含むArrayListを作成し、返される要素は、そのcollectionの反復器に従って返される順序(特にCollectionのtoArray()メソッド)

である.

   //      collection ArrayList 
    public ArrayList(Collection extends E> c) {
        //      collection         ，       collection               
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
           //         0（     ）
            if (elementData.getClass() != Object[].class)
                //  elementData  ，     null   （    ），           ，   Object[] 
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

4ツールクラス

trimToSize():現在の容量値を実要素個数

とする.

 public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            //        
            elementData = Arrays.copyOf(elementData, size);
        }
    }

public void ensureCapacity(int minCapacity):拡張方法、ArrayListは新規要素毎に容量サイズ検出判定を行い、新規後要素の個数がArrayListの容量を超えると、新規要素のニーズを満たす拡張を行う

.

public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != EMPTY_ELEMENTDATA)
            ? 0
            //       ，elementData    ，  minExpand 10
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

次にensureExplicitCapacity()を見て、

private void ensureExplicitCapacity(int minCapacity) {
    //         ， fail-fast    ，         ，          （      add，remove ），  List     ，
    //     List   （  List  add，remove ），  List     ，   ConcurrentModificationException
        modCount++;

        if (minCapacity - elementData.length > 0)
           //           ，    grow  ，    
            grow(minCapacity);
    }

fail-fastメカニズム
実際の拡張方法grow()

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //        =       1.5 ，  1         1.5 
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
             //    
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

1.5倍の神秘的な法則:一度の拡張容量が大きすぎる(例えば2.5倍)ため、より多くのメモリを1.5倍浪費する可能性がある:最大33%2.5倍浪費する:最大60%3.5倍浪費する:71%浪費するが、一度の拡張容量が小さすぎて、何度も配列にメモリを再分配する必要があり、対性エネルギー消費が深刻である.そのため、1.5倍がちょうどいいので、パフォーマンスのニーズを満たすだけでなく、メモリの消費量も大きくありません.
未完
新規:
更新されていません