網頁

2020/7/11

Java 8 ArrayList.add(E e) 原始碼分析

本篇分析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),會遞增父類AbstractListmodCount的值,此用來防止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)


沒有留言:

張貼留言