ArrayListの実現原理を深く分析する

ArrayListは動的配列であり、配列Arrayよりも多くの方法を提供し、動的に増加し、要素を削除し、容量を変更する.
単純な応用

public class ArrayListStudy {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        arrayList.add(1);
        arrayList.add(2);
        System.out.println("OUT1: " + arrayList);
        arrayList.set(0, 100);
        System.out.println("OUT2: " + arrayList);
        arrayList.remove(0);
        System.out.println("OUT3: " + arrayList);
        arrayList.clear();
        System.out.println("OUT4: " + arrayList);
    }
}

----------
OUT1: [1, 2]
OUT2: [100, 2]
OUT3: [2]
OUT4: []

上記のコードからArrayListの一般的な使用出力が分かるようになりましたが、ここで疑問はありませんか?

初期化容量はいくらですか?

拡張を開始するのに適していますか?

拡張時の割合はいくらですか?

具体的にはどのように拡張を実現しますか?

次に,ArrayListの無パラメトリック構造関数を用いて初期化したときの探索を行う.

ArrayList<Integer> arrayList = new ArrayList<Integer>();

ソースの表示:

//        ，            ，     elementData
private static final Object[] EMPTY_ELEMENTDATA = {};
//         
private transient Object[] elementData;
public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }

このことから,このときのメモリ要素配列elementDataの長さは0であるため,コンテナ容量は0であることが分かる.次にaddメソッドを呼び出してコンテナに要素を追加します

arrayList.add(1);

ソースの表示:

//            
private int size;
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
private void ensureCapacityInternal(int minCapacity) {
        //            0，            10   
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
private void ensureExplicitCapacity(int minCapacity) {
        //          ,      AbstractList   
        modCount++;

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

これにより、addメソッドを呼び出してArrayListに要素を追加するたびに、コンテナはensureCapacityInternalメソッドを呼び出して、このときの容量がこの要素を収容できることを確保し、収容できない場合は拡張する.このとき容量が0の場合、10に拡張します.このとき容量が0でなければ、どのくらい拡張されますか?ソースコード:

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //    =     + （    / 2）    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);
    }

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

このことから、現在の容量の1.5倍の拡張が分かるとともに、その限界容量は2147483647であることが分かった.拡張容量の容量を特定した後、具体的にどのように拡張容量を実現しますか?ソースの表示を続行します.

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) {
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        //        C++     ，                 ，          
        //System.arraycopy   
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

このことから,拡張時にコンテナは現在計算されている容量の配列を再作成し,JDK下位層のC++コードを呼び出して一括配列コピー操作を完了することが分かった.小猿はここまで分析して、まだ各位の学友が自分で分析することを分析していないで、実はソースコードはそんなに恐ろしくなくて、注意深く見に行くだけでいいです.もし間違っているところがあれば、私に伝言を残してください.もっとすばらしいです.loveに注目してください.coding微信公衆番号.