1 概述 ArrayList實現了List介面，是 順序容器，允許放入null元素 有一個容量(capacity)，表示底層數組的實際大小。如果容量不足，容器會 自動增大底層數組的大小 支持泛型，泛型擦除後，容器的元素都是 Object類型 ArrayList沒有實現同步(synchronized) ...
目錄
1 概述
- ArrayList實現了List介面，是 順序容器，允許放入null元素
- 有一個容量(capacity)，表示底層數組的實際大小。如果容量不足，容器會 自動增大底層數組的大小
- 支持泛型，泛型擦除後，容器的元素都是 Object類型
- ArrayList沒有實現同步(synchronized)，因此它是 線程不安全的。（vector線程安全）
- 關於數組：一旦數組初始化完成，則長度不可改變 因此ArrayList擴容時會涉及數組的拷貝
2 底層數據結構
兩個重要成員變數
- Object[] elementData：
存儲列表元素的數組；該數組的長度就是列表的容量
列表的容量是指它所能存儲元素的最大個數
- size：
列表的大小。指當前列表包含的元素個數，跟容量不是一個概念
size 跟 elementData數組長度是不一樣的。elementData 允許長度大於元素的個數
transient Object[] elementData; //存儲列表元素的數組
private int size;//元素的數量
protected transient int modCount = 0; //list的修改次數
3 構造函數
有三個構造函數：
- 指定初始容量大小時，創建一個容量為參數的Object數組，並賦值給數據數組
- 不指定初始容量大小時，數據數組賦值為一個無限容量的空數組
- 構造參數為集合類型，將參數轉換成Object類型數組，並賦值給數據數組
- 註意，只有當第一次add元素時，才會指定數組的長度
參照源碼：
//指定初始容量大小時，創建一個容量為參數的Object數組，並賦值給數據數組
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;
}
// 構造參數為集合類型，將參數轉換成Object類型數組，並賦值給數據數組
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
4 自動擴容
- 添加元素時，會判斷添加後是否超出當前數組長度，超出則會執行數組擴容；
- 數組擴容時，會將老數組中的元素重新 拷貝一份到新的數組中。（因為數組長度不可變，因此需要創建新數組）
- 數組執行擴容，擴容後的容量為擴容前的 1.5倍
- 儘可能評估所需要容量的大小，避免擴容。（因為擴容占用更多的記憶體）
參考源碼:
重點！！！！！：添加前，都判斷是否需要擴容：（如果size+1後，超過elementData的長度，則執行擴容，擴容為原來的1.5倍）
public boolean add(E e) {
ensureCapacityInternal(size + 1); // size 初始化時是0，
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//計算所需容量:第一次添加時，容量為10；反則，容量為當前長度+1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY = 10,即第一次添加時，數組長度變為10
}
return minCapacity;//如果數組不為空時，最小長度是當前長度+1
}
//再次計算數組所需容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//列表修改次數遞增
//所需容量大於數組的長度,則執行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//擴容，數組的記憶體狀態已經發生變化了
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);// 新的長度為舊長度的1.5倍 【右移1位（除以2）】
if (newCapacity - minCapacity < 0) // 如果擴容後的長度小於所需要的最小長度，則使用最小長度(基本不會發生)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //這裡是極限的情況，即逼近數組分配的最大記憶體空間
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity); // 執行數組拷貝
}
5 set() get() remove()
- set()方法也就變得非常簡單，直接對數組的指定位置賦值即可。
public E set(int index, E element) {
rangeCheck(index);//下標越界檢查
E oldValue = elementData(index);
elementData[index] = element;//賦值到指定位置，複製的僅僅是引用
return oldValue;//返回原先位置上的元素
}
- get()方法同樣很簡單，唯一要註意的是由於底層數組是Object[]，得到元素後需要進行類型轉換。
public E get(int index) {
rangeCheck(index);
return (E) elementData[index];//註意類型轉換
}
- remove()方法也有兩個版本，一個是remove(int index)刪除指定位置的元素，另一個是remove(Object o)刪除第一個滿足o.equals(elementData[index])的元素。刪除操作是add()操作的逆過程，需要將刪除點之後的元素向前移動一個位置。需要註意的是為了讓GC起作用，必須顯式的為最後一個位置賦null值。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; //清除該位置的引用，讓GC起作用
return oldValue;
}
6 Fail-Fast機制
ArrayList也採用了快速失敗的機制，通過記錄 modCount 參數來實現。在面對併發的修改時，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發生任意不確定行為的風險。
