JDK1.8 ArrayList拡張分析

ArrayListは容量の適応的増加(As elements are added to an ArrayList,its capacity grows automatically)を実現できる.JDK 1を通過する.8のArrayListのソースコードを分析する:
ArrayListの関連定義
ArrayListの下位層はObjectタイプの配列で実現される.
まず、デフォルトの初期容量を10に定義します.

private static final int DEFAULT_CAPACITY = 10;

さらに、空のインスタンスに使用する空の配列インスタンスを定義する

private static final Object[] EMPTY_ELEMENTDATA = {};

さらに、ArrayListオブジェクトリストを格納するためにシーケンス化されていない配列elementDataが定義されている

/**
 * The capacity of the ArrayList is the length of this array buffer.
 */
transient Object[] elementData;

なお、ArrayListのsize変数を定義している

/**
     * The size of the ArrayList (the number of elements it contains).
 */
private int size;

ArrayListの自動拡張メカニズムを実現するために,javaは配列のlengthを区別するためにcapacityとsize概念を導入した.Capacityは最下位配列の長さ(length)、sizeは格納されたリストオブジェクトの数でprivateに設定されています.
ArrayListの初期化
ArrayListは3つの方式で初期化され、構築方法のソースコードは以下の通りである.
1.指定した初期容量で空のリストを作成

/**
     * Constructs an empty list with the specified initial capacity.
     */
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //                  
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+  initialCapacity);
        }
    }

2.初期容量10を使用して空のリストを作成する(パラメータなし)

/**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

3.指定されたcollection要素を含むリストを構築します.これらの要素は、そのセットの反復器を使用して順番に返されます.
指定したセットがnullの場合、throws NullPointerException.

public ArrayList(Collection extends E> c) {

        elementData = c.toArray();// Collection     elementData
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

ArrayList拡張
無パラメータ構造を例にとると,初期配列容量は10である.本当に配列を追加すると、容量が本当に割り当てられます.すなわち、配列に最初の要素を追加すると、配列容量は10に拡張されます.
1.add(E e)法による入口分析

public boolean add(E e) {
       //      ，   ensureCapacityInternal  
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;//     ，  size
        return true;
    }

2.ensureCapacityInternalメソッドensureCapacityInternalに入ります(「内部容量の確保」)

private void ensureCapacityInternal(int minCapacity) {
        //         
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
           //      ， DEFAULT_CAPACITY( 10) minCapacity         minCapacity
           // minCapaciy   10
        }
        ensureExplicitCapacity(minCapacity);
        //  ensureExplicitCapacity  
    }

空のリストadd()の1番目の要素をデバッグすると、元のminCapacityは1であり、Math.max()メソッドの比較後,minCapacityは10であった.
ただし、add()の2番目の要素の場合、配列は空ではなく、ensureExplicitCapacity(minCapacity)に直接入ります(この場合minCapacityは2).
3.ensureExplicitCapacityメソッドへのアクセス
配列が空であるかどうかにかかわらず、ensureExplicitCapacityメソッドに入ります.

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//   ArrayList   AbstractList，          
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
        //       (elementData.length)         (minCapacity)，   
            grow(minCapacity);
    }

1番目の要素をaddする場合、elementData.length(0です.この場合も空のリストなので)はminCapacity(10)よりも小さく、grow(minCapacity)メソッド(minCapacityは10)に入ります.
addの2番目の要素の場合、デバッグではminCapacityが2である、elementDataであることがわかる.length(すなわち容量)は、最初の要素を追加すると10に拡張され、minCapacityよりも大きくなり、growメソッドは実行されません.配列容量はまだ10です.
したがって,3,4・・・10番目の要素を追加した場合もgrowメソッドは実行されず,配列容量はいずれも10である.
11番目の要素を追加するまで、minCapacity(11)はelementDataよりも大きい.length(10)は大きいです.grow法に入って拡張する.
4.growメソッドへの拡張

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//       size   
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //           2，          
        //            1.5 
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // minCapacity   newCapacity                （   ）。
        //         1   。1.5 oldCapacity 0，  newCapacity     10
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity); 
         //            size，  hugeCapacity  
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
        //  ，                。

    }

addの1番目の要素の場合、oldCapacityは0であり、比較後、最初のif判定が成立し、newCapacity=minCapacity(10)となる.しかし、2番目のif判断は成立しない.すなわち、newCapacityはMAX_に及ばない.ARRAY_SIZEが大きいと、hugeCapacityメソッドには入りません.配列容量は10であり,add法ではreturn true,sizeは1に増加した.
add 11番目の要素がgrowメソッドに入ると,newCapacityは15であり,minCapacity(11)よりも大きく,最初のif判定は成立しない.新しい容量は配列の最大sizeより大きくなく、hugeCapacityメソッドには入りません.配列容量は15に拡張され,add法ではreturn true,sizeは11に増加した.
このように推すと・・・
5.新しい容量がMAX_より大きい場合ARRAY_SIZE、hugeCapacityメソッドに入ります

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
            // minCapacity MAX_ARRAY_SIZE    
            // minCapacity ， Integer.MAX_VALUE        
            // MAX_ARRAY_SIZE ， MAX_ARRAY_SIZE        
    }

したがって、ArrayListのようにオブジェクトを追加する場合、新しい配列のサイズを決定すると、Arraysが呼び出される.copyOf()メソッドでは、元の配列のコピーを適切な長さ(newCapacity)で新規作成し、この新規配列を指す元の配列を変更します.JAvaごみ回収メカニズムは、元の配列を自動的に回収します.これにより、一定のリソースが消費されます.
したがって、ArrayListを初期化する際には、初期サイズを推定することが望ましい.
6.新しい要素からの増分の割当て回数を減らすために、add大量要素の前にensureCapacityメソッドを使用することが望ましい.
ソースコードは次のとおりです.

/**
 * 
An application can increase the capacity of an ArrayList instance
 * before adding a large number of elements using the ensureCapacity
 * operation.  This may reduce the amount of incremental reallocation.
 */

     public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

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

作者:AmorFatiYJリンク:https://www.jianshu.com/p/38e3d67bcc26出典:簡書の著作権は作者の所有である.商業転載は著者に連絡して許可を得てください.非商業転載は出典を明記してください.