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;
①等しいか否かを判断し、elementData
とDEFAULTCAPACITY_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);
}
}
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
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);
}
}
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;
}
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
list.add("111");
public boolean add(E e) {
ensureCapacityInternal(size + 1); // , size , 1 size 1,
elementData[size++] = e;
return true;
}
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;
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)// ,
grow(minCapacity);
}
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<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);
}
}