ArrayList常用Api分析及注意事項

• 2022 年 5 月 23 日
• 筆記
• JAVA

數組（定長，有序的，隨機訪問)。ArrayList是Java在數組的基礎上進行衍生出來的Java里的一種數據結構，它在擁有數據的特性之外，增加了可變性 （動態數組）。

屬性

三種構造初始化

/**

帶有參數的構造方法，

如果長度為0 則給一個默認的常量。

*/
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 ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

   public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

分析

以上三種構建，兩種有參，一種無參。主要區別就是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA和 EMPTY_ELEMENTDATA在不同場景分別給值。
EMPTY_ELEMENTDATA是帶參數的構建函數里長度為0的默認共享數組
DEFAULTCAPACITY_EMPTY_ELEMENTDATA是不帶參數構造函數里長度為0的共享數組
對比老版本的JDK來看，會對初始化數組的時候解決是數度長度為空的情況下會 new Object[initialCapatity]的情況，減少不必要的記憶體開支。
在擴容機制也會針對不同的構造出的數組進行不同的擴容機制。

Add方法

    public boolean add(E e) {
		//確保容量夠不夠，擴容機制
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
	
    // step 1
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

	// step 2. 計算容量
    private static int calculateCapacity(Object[] elementData, int minCapacity) 	{
		//判斷是否是無參構造來的，為10個容量大小
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
		//否則就給即將增長的長度
        return minCapacity;
     }
	
	
	// step 3
    private void ensureExplicitCapacity(int minCapacity) {
		//修改次數
        modCount++;

        // 即將增長的長度比現的數組長度大就擴容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

	// step 4
    private void grow(int minCapacity) {
        //原始長度
        int oldCapacity = elementData.length;
		//新長度 = 原始長度 + （原始長度/2)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
		
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
		//盡量不擴容到 Intege 的最大值， 因為有些Vm的設計超過 MAX_ARRAY_SIZE 可能會 OOM錯誤 （OutOfMemoryError: Requested array size exceeds VM limit）
        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);
    }

分析

1. 從add函數，可以看出來，每次擴容都是本身的 0.5 倍
2. 最大可以擴容到 Intege最大值，但也是在實際元素數量真的超過 MAX_ARRAY_SIZE的情況下。
3. 建立不超過MAX_ARRAY_SIZE的原因是 OutOfMemoryError: Requested array size exceeds VM limit
4. 為了避免開闢過多的數組空間，建立選擇帶參數的構造函數，以量申請。

Remove方法

藉助了系統函數

/**
         *    第一個參數是要被複制的數組
         *
         * 　　第二個參數是被複制的數字開始複製的下標
         *
         * 　　第三個參數是目標數組，也就是要把數據放進來的數組
         *
         * 　　第四個參數是從目標數組第幾個下標開始放入數據
         *
         * 　　第五個參數表示從被複制的數組中拿幾個數值放到目標數組中
         */

public static native void arraycopy(Object src,  int  srcPos,
									Object dest, int destPos,
                                        int length);

把最後一個元素置為null, size = size -1

elementData[--size] = null; // clear to let GC do its work

注意事項

1. 禁止在 for``foreach里刪除元素。
2. ArrayList在多執行緒環境中是不安全的