本篇分析Java 8 java.util.ArrayList.add(int index, E element)的原始碼。
節錄原始碼如下。
java.util.ArrayList
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
transient Object[] elementData; // non-private to simplify nested class access // 實際用來裝載元素的陣列空間
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity)); // 複製原elementData陣列並增加陣列長度
}
// (2)
private Object[] grow() {
return grow(size + 1); // 至少增加原長度加1
}
// (3)
/**
* 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);
}
// (1)
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
// (2)
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
ArrayList.add(int index, E element)插入元素到指定索引位置(1)，先呼叫rangeCheckForAdd()檢查指定的索引位置index是否超出範圍，若超出範圍丟出IndexOutOfBoundsException。
然後呼叫grow()(2)視陣列空間是否足夠來增加儲存元素的elementData陣列長度，若陣列長度不足預設新增%50的長度空間(3)。
接著把利用System.arraycopy()把elementData從index開始及之後的每個元素往後1個位置複製。這也是為什麼ArrayList插入或刪除時效能比LinkedList差的原因。
以一個元素長度為10且elementData滿載的情況來看，插入一個元素的陣列變化圖示如下。
0 1 2 3 4 5 6 7 8 9
+---+---+---+---+---+---+---+---+---+---+
| a | b | c | d | e | f | g | h | i | j | elementData = {a,b,c,d,e,f,g,h,i,j}
+---+---+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| a | b | c | d | e | f | g | h | i | j | | | | | | grow()
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| a | b | c | d | e | | f | g | h | i | j | | | | | System.arraycopy(elementData, index,
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ elementData, index + 1,
s - index)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| a | b | c | d | e | X | f | g | h | i | j | | | | | elementData[index] = element
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
沒有留言:
張貼留言