本篇分析Java 8java.util.ArrayList.add(E e)的原始碼。
節錄原始碼如下。
java.util.ArrayList
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final int DEFAULT_CAPACITY = 10; // 新增元素時的預設陣列長度
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 預設的空陣列
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access // 實際用來裝載元素的陣列空間
private int size; // ArrayList目前裝載的元素長度
// (1)
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 建立ArrayList的初始陣列為空陣列
}
/**
* The maximum size of array to allocate (unless necessary).
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 最大陣列長度
// (5)
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity)); // 複製原elementData陣列並增加陣列長度
}
// (4)
private Object[] grow() {
return grow(size + 1); // 至少增加原長度在加1
}
// (6)
/**
* Returns a capacity at least as large as the given minimum capacity.
* Returns the current capacity increased by 50% if that suffices.
* Will not return a capacity greater than MAX_ARRAY_SIZE unless
* the given minimum capacity is greater than MAX_ARRAY_SIZE.
*
* @param minCapacity the desired minimum capacity
* @throws OutOfMemoryError if minCapacity is less than zero
*/
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; // 陣列原有長度
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新長度 = 舊長度 + 舊長度/2 (shift bit operation)
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // 若未新增過元素，則取新增長度或預設長度(10)的最大
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0) // 新的陣列長度不能超過最大陣列長度
? newCapacity
: hugeCapacity(minCapacity);
}
// (3)
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow(); // 增加裝載元素的elementData陣列空間
elementData[s] = e;
size = s + 1;
}
// (2)
public boolean add(E e) {
modCount++; // 此為父類AbstractList的屬性，用來防止併行修改(concurrent modification)
add(e, elementData, size);
return true; // 新增成功返為true
}
}
當建立一個空的ArrayList的實例(1)並呼叫add(E e)(2)，會遞增父類AbstractList的modCount的值，此用來防止ArrayList被併行修改。
ArrayList內部其實是利用一個陣列Object[] elementData來裝載元素。此陣列所佔的空間大小才是實際使用的空間大小，且不一定等於ArrayList.size()的長度。換句話說ArrayList.size()不代表實際使用的空間長度，僅是反映目前裝載的元素長度而已。
從Object[] elementData可看出為什麼ArrayList的元素只能是物件(Object)而不能是原始型別(primitive type)，因為原始型別無法達到泛型(Geneircs)的效果。
當新增元素時，若目前的元素長度size已經等於elementData(3)，則會先增加elementData的長度(5)。預設會增加原有陣列長度大小的1.5倍。例如原本陣列長度10，則新增後的陣列長度為15。(6)
沒有留言:
張貼留言