ArrayListとLinkedListのセットの下位ソース分析

16840 ワード

ArrayList下位層


ArrayListコレクションはオブジェクトを作成した後、実はArrayListクラスの中で1つのクラスを継承し、いくつかのインタフェースを実現した.
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

テストクラスでArrayListクラスの無パラメトリック構造を呼び出してテストクラスを書きます.
public static void main(String[] args) {
		ArrayList<String> list= new ArrayList();
		list.add("111");
		list.add("222");
		for (String str : list) {
			System.out.println(str);
		}
	}

しかし、ArrayListクラスでは、この非パラメトリック構造が本クラスの有パラメトリック非パラメトリック構造を呼び出し続けることを発見しました.
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

参照構造:
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

無パラメトリック構造から定数DEFAULTCAPACITY_EMPTY_ELEMENTDATAが変数elementDataに与えられていることが判明し、その定数の声明を知りたくなり、位置決めによって発見された.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

これは、カプセル化されたObject配列の静的定数であり、この定数には値がなく、再配置によってelementDataコードが見つかった.
transient Object[] elementData;
transient修飾変数のelementDataはシーケンス化されていない(一応覚えておいて、後で述べる)ここまで来ると、値のない定数がelementDataに与えられていることがわかりにくくないので、elementDataも値のないものは次のように見えます.
private int size;

このときのsizeのデフォルトは0(注記)でテストクラスに戻ります.
list.add("111");

このときのaddからArrayListクラスに位置する:
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // ,  size , 1 size 1, 
    elementData[size++] = e;
    return true;
}
ensureCapacityInternalから配列拡張にジャンプできるメソッドコード:
private void ensureCapacityInternal(int minCapacity) {
   if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
   }
   ensureExplicitCapacity(minCapacity);
}

次のようになります.
private static final int DEFAULT_CAPACITY = 10;

①等しいか否かを判断し、elementDataDEFAULTCAPACITY_EMPTY_ELEMENTDATAの両方の値が同じであれば、得られた値を判断実行コードブロック中のMath.max()に入れて方法中の最大値をminCapacityに付与する.2つの値が等しくない場合は、ensureExplicitCapacityメソッドを直接呼び出し、このメソッドを介して次の拡張コードにナビゲートします.
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)// , 
    	grow(minCapacity);
}

しかし、拡張もgrowメソッドを呼び出しただけであることに気づき、再び位置決めしました.
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;	// 
    int newCapacity = oldCapacity + (oldCapacity >> 1);	// + = 
    if (newCapacity - minCapacity < 0)	// 0
        newCapacity = minCapacity;	// ( )
    if (newCapacity - MAX_ARRAY_SIZE > 0)// 0
        newCapacity = hugeCapacity(minCapacity);// 
    elementData = Arrays.copyOf(elementData, newCapacity);
}

突然、これが本当に拡張を実行する最下位であることがわかりました.
もちろん、オブジェクトを作成するときに配列の長さを宣言することもできます.このとき、ArrayListのパラメータ構造を使用します.
ArrayList<String> list= new ArrayList<>(20);// 20
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);
    }
}