Java学習ノート---ArrayListの動的拡張

今日Javaが搭乗したとき、こんな問題がありました.
このテーマでは、入力された配列要素の個数が配列長を超えると、配列は自動的に5要素の容量を増加し、すなわち配列長が5要素増加する長さ可変の整数配列Intarrayを定義する必要があります.
すなわち、ArrayListのような自動拡張int型の配列を実現する.ArrayListに類似する以上、ArrayListがどのように動的に拡張するかを見てみましょう.
ArrayListは集合クラスListの配列ベースの実装である、すなわち、ArrayListの下位層は実質的にObject[]配列である.しかし配列は一定長であるが、我々がArrayListを使用する際にこのような感じがしないのは、内部の配列拡張操作をカプセル化しているため、ArrayListがどのように安全に拡張を実現するかが注目点となっている.
1.ArrayList下位配列容量の初期化
ArrayListの初期化時には、パラメータinitialCapacityで下位配列の初期サイズを指定することができる.その構築方法のソースコードは次のように選択されます.

// ArrayList      10
private static final int DEFAULT_CAPACITY = 10;

//     Object[]      
private static final Object[] EMPTY_ELEMENTDATA = {};

//        ,   initialCapacity   Object[]            .
//   initialCapacity       ,          Object  .
//   initialCapacity  0,        Object[]  .
//   initialCapacity  0,      IllegalArgumentException  .
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);
    }
}

//                 Object[]  .
//     JDK1.6 ArrayList                10 Object[]  .(emmm,      Java          ..)
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

2.ArrayList下位配列の拡張
動的拡張に関して、ArrayListは一つの方法void ensureCapacity(int minCapacity)を暴露し、その方法名の中国語の意味は容量を保証することである.このメソッドを呼び出すことでObject[]配列のサイズを設定できますが、このメソッドではArrayListの下位配列の拡張に関する一連のメソッドが呼び出され、ソースコードを見てみましょう.

// ArrayList                
//   minCapacity          
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;

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

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

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

	//                     (minCapacity)       grow()
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

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

//     
// >>         ,      newCapacity = oldCapacity + 0.5 * oldCapacity(  1.5   )
// JDK1.7       ,        
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}

前にそんなにたくさん言ったのに、実はこの一言のために!!!このコードはArrayList配列拡張の真の操作です!!!

elementData = Arrays.copyOf(elementData, newCapacity);

このコードの意味は、newCapacityサイズの空間を再割り当て、元の配列の要素をコピーすることである.
もっとはっきり見えるようにArraysを見てみましょうcopyOf()このメソッドのソースコード:

//                          copyOf()  
public static  T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static  T[] copyOf(U[] original, int newLength, Class extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    //         ,        
    System.arraycopy(original, 0, copy, 0,
            Math.min(original.length, newLength));
    return copy;
}

2019/03/15補足:
最近、後輩が仁さんに面接されて、ArrayListのダイナミックな拡張を聞かれて、私が前に書いたこのブログを思い出して、振り返ってみると、本当に知っていますが、なぜか分かりません.
ArrayListの拡張はArraysを呼び出すことしか知られていなかった.copyOf()メソッドは新しい配列を作成したが,Arraysを注意深く研究しなかった.copyOf()にはいったいどんなものがあるのか.今日ソースコードを見てみると、ArrayList拡張時に新しい配列を作成する場合と、newで直接作成する場合と、反射で作成する場合の2つがあります.具体的にはArraysを見てみましょう.copyOf()メソッドのこの行のコード:

   //     ArrayList        Object   ，    new      ，
   //      ，        ， newInstance()   。
   T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);

このように見ると,ArrayListの下位配列の動的拡張について明確な認識が得られたのではないか.実はこの操作はC言語のrealloc()関数に似ている.realloc()関数に言及した以上、その原理について説明します.
*realloc(void__ptr,size_t__size):割り当てられたメモリ領域を変更する、すなわちmalloc()関数で割り当てられたメモリ領域のサイズを変更する.
割り当てられたメモリを減少すると、reallocはインデックスを変更する情報にすぎない.
割り当てられたメモリを拡大する場合、1)現在のメモリセグメントの後ろに十分なメモリ領域がある場合、このメモリ領域を直接拡張すると、realloc()は元のポインタに戻る.2)現在のメモリセグメントの後の空きバイトが足りない場合は、その要求を満たす最初のメモリブロックを使用して、現在のデータを新しいメモリブロックにコピーし、元のメモリブロックを解放する、新しいメモリブロックヘッダアドレスに戻る.3)申請に失敗した場合はNULLに戻るが、この場合も元のポインタは有効である.