ArrayList動的展開のソースコード

ArrayListは「自動的に容量を拡張する配列」の一種と理解できます。では、問題は......？

まず、ArrayListのソースコードを開いてください。最初の質問に対して、add(E e)メソッドに目を向けることができます：

 public boolean add(E e) {
 ensureCapacityInternal(size + 1); // Increments modCount!!
 elementData[size++] = e;
 return true;
 }
 // ここでのサイズは、配列の長さではなく、ArrayListの長さを表していることに注意。

ソースコードは実にシンプルで、見ての通り、拡張はsecureCapacityInternalメソッドで処理されます：

 private void ensureCapacityInternal(int minCapacity) {
 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 }
 ensureExplicitCapacity(minCapacity);
 }
 //ここで、elementDataはデータを格納するオブジェクトであり、ArrayListは実際には配列をカプセル化するレイヤーである。
 //minCapacityは最小値DEFAULTを決定することに注意。_CAPACITY，つまり10

secureCapacityInternalメソッドもまた、謎のベールを脱ぎ続けています。

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

 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);
 }

ようやく山の素顔を見ることができました。まず最初に、minCapacityの値が何であるかを確認してください。add(E e)メソッドのこの行を見てください：

 ensureCapacityInternal(size + 1)

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

配列の初期化メソッドがパラメータなしのnew ArrayList()を呼び出すと仮定すると、この2行のコードで処理されるロジックは次のようになります：

oldCapacity = 0， newCapacity = 0 + 0000>>1 = 0 + ;
oldCapacity = 1， newCapacity = 1 + 0001>>1 = 1 + ;
oldCapacity = 2， newCapacity = 2 + 0010>>1 = 2 + ;
oldCapacity = 4， newCapacity = 4 + 0100>>1 = 4 + ;
oldCapacity = 7， newCapacity = 7 + 0111>>1 = 7 + ;
oldCapacity = 11， newCapacity = >>1 =  = 16;
oldCapacity = 17， newCapacity = 1>>1 =  = 25;
...

ビット演算を理解していなくても、newCapacityはoldCapacityの1.5倍のサイズであると一般化できます。つまり、add(E e)メソッドが実行されるたびに、配列の容量は元のサイズの1.5倍に拡張されます。

その他の読書法

addAll(Collection<? extendsE> c)

 public boolean addAll(Collection<? extends E> c) {
 Object[] a = c.toArray();
 int numNew = a.length;
 ensureCapacityInternal(size + numNew); // Increments modCount
 System.arraycopy(a, 0, elementData, size, numNew);
 size += numNew;
 return numNew != 0;
 }

add(E e) と同じように、まず配列を展開し、次に配列をマージします。展開の基本的なロジック： newCapacity は、まず元の配列の 1.5 倍に展開し、次に配列の現在の容量と新しいサイズとを比較して、大きい方の値を取って展開します。

add(int index,E element)

 public void add(int index, E element) {
 if (index > size || index < 0)
 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 ensureCapacityInternal(size + 1); // Increments modCount!!
 System.arraycopy(elementData, index, elementData, index + 1,
 size - index);
 elementData[index] = element;
 size++;
 }

このメソッドは、配列のコピーを作成します。まず、インデックスから末尾の1つ後ろの位置に配列をシフトし、次にインデックス位置に要素を代入します。