ArrayList 是實(shí)現(xiàn) List 接口的動(dòng)態(tài)數(shù)組，所謂動(dòng)態(tài)就是它的大小是可變的。實(shí)現(xiàn)了所有可選列表操作，并允許包括 null 在內(nèi)的所有元素。除了實(shí)現(xiàn) List 接口外，此類還提供一些方法來操作內(nèi)部用來存儲(chǔ)列表的數(shù)組的大小。
每個(gè) ArrayList 實(shí)例都有一個(gè)容量，該容量是指用來存儲(chǔ)列表元素的數(shù)組的大小。默認(rèn)初始容量為 10。隨著 ArrayList 中元素的增加，它的容量也會(huì)不斷的自動(dòng)增長(zhǎng)。在每次添加新的元素時(shí)，ArrayList 都會(huì)檢查是否需要進(jìn)行擴(kuò)容操作，擴(kuò)容操作帶來數(shù)據(jù)向新數(shù)組的重新拷貝，所以如果我們知道具體業(yè)務(wù)數(shù)據(jù)量，在構(gòu)造 ArrayList 時(shí)可以給 ArrayList 指定一個(gè)初始容量，這樣就會(huì)減少擴(kuò)容時(shí)數(shù)據(jù)的拷貝問題。當(dāng)然在添加大量元素前，應(yīng)用程序也可以使用 ensureCapacity 操作來增加 ArrayList 實(shí)例的容量，這可以減少遞增式再分配的數(shù)量。
注意，ArrayList 實(shí)現(xiàn)不是同步的。如果多個(gè)線程同時(shí)訪問一個(gè) ArrayList 實(shí)例，而其中至少一個(gè)線程從結(jié)構(gòu)上修改了列表，那么它必須保持外部同步。所以為了保證同步，最好的辦法是在創(chuàng)建時(shí)完成，以防止意外對(duì)列表進(jìn)行不同步的訪問：
List list = Collections.synchronizedList(new ArrayList(…));
ArrayList 我們使用的實(shí)在是太多了，非常熟悉，所以在這里將不介紹它的使用方法。ArrayList 是實(shí)現(xiàn) List 接口的，底層采用數(shù)組實(shí)現(xiàn)，所以它的操作基本上都是基于對(duì)數(shù)組的操作。
private transient Object[] elementData;
transient？？為 Java 關(guān)鍵字，為變量修飾符，如果用 transient 聲明一個(gè)實(shí)例變量，當(dāng)對(duì)象存儲(chǔ)時(shí)，它的值不需要維持。Java 的 serialization 提供了一種持久化對(duì)象實(shí)例的機(jī)制。當(dāng)持久化對(duì)象時(shí)，可能有一個(gè)特殊的對(duì)象數(shù)據(jù)成員，我們不想用 serialization 機(jī)制來保存它。為了在一個(gè)特定對(duì)象的一個(gè)域上關(guān)閉 serialization，可以在這個(gè)域前加上關(guān)鍵字 transient。當(dāng)一個(gè)對(duì)象被序列化的時(shí)候，transient 型變量的值不包括在序列化的表示中，然而非 transient 型的變量是被包括進(jìn)去的。
這里 Object[] elementData，就是我們的 ArrayList 容器，下面介紹的基本操作都是基于該 elementData 變量來進(jìn)行操作的。
ArrayList 提供了三個(gè)構(gòu)造函數(shù)：
ArrayList()：默認(rèn)構(gòu)造函數(shù)，提供初始容量為 10 的空列表。
ArrayList(int initialCapacity)：構(gòu)造一個(gè)具有指定初始容量的空列表。
ArrayList(Collection<? extends E> c)：構(gòu)造一個(gè)包含指定 collection 的元素的列表，這些元素是按照該 collection 的迭代器返回它們的順序排列的。
/**
* 構(gòu)造一個(gè)初始容量為 10 的空列表
*/
public ArrayList() {
this(10);
}
/**
* 構(gòu)造一個(gè)具有指定初始容量的空列表。
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "
+ initialCapacity);
this.elementData = new Object [initialCapacity];
}
/**
* 構(gòu)造一個(gè)包含指定 collection 的元素的列表，這些元素是按照該 collection 的迭代器返回它們的順序排列的。
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
ArrayList 提供了 add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)、set(int index, E element) 這個(gè)五個(gè)方法來實(shí)現(xiàn) ArrayList 增加。
add(E e)：將指定的元素添加到此列表的尾部。
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
這里 ensureCapacity() 方法是對(duì) ArrayList 集合進(jìn)行擴(kuò)容操作，elementData(size++) = e，將列表末尾元素指向e。
add(int index, E element)：將指定的元素插入此列表中的指定位置。
public void add(int index, E element) {
//判斷索引位置是否正確
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
//擴(kuò)容檢測(cè)
ensureCapacity(size+1);
/*
* 對(duì)源數(shù)組進(jìn)行復(fù)制處理（位移），從index + 1到size-index。
* 主要目的就是空出index位置供數(shù)據(jù)插入，
* 即向右移動(dòng)當(dāng)前位于該位置的元素以及所有后續(xù)元素。
*/
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//在指定位置賦值
elementData[index] = element;
size++;
}
在這個(gè)方法中最根本的方法就是 System.arraycopy() 方法，該方法的根本目的就是將 index 位置空出來以供新數(shù)據(jù)插入，這里需要進(jìn)行數(shù)組數(shù)據(jù)的右移，這是非常麻煩和耗時(shí)的，所以如果指定的數(shù)據(jù)集合需要進(jìn)行大量插入（中間插入）操作，推薦使用 LinkedList。
addAll(Collection<? extends E> c)：按照指定 collection 的迭代器所返回的元素順序，將該 collection 中的所有元素添加到此列表的尾部。
public boolean addAll(Collection<? extends E> c) {
// 將集合C轉(zhuǎn)換成數(shù)組
Object[] a = c.toArray();
int numNew = a.length;
// 擴(kuò)容處理，大小為size + numNew
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
這個(gè)方法無非就是使用 System.arraycopy() 方法將 C 集合(先準(zhǔn)換為數(shù)組)里面的數(shù)據(jù)復(fù)制到 elementData 數(shù)組中。這里就稍微介紹下 System.arraycopy()，因?yàn)橄旅孢€將大量用到該方法。該方法的原型為：public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)。它的根本目的就是進(jìn)行數(shù)組元素的復(fù)制。即從指定源數(shù)組中復(fù)制一個(gè)數(shù)組，復(fù)制從指定的位置開始，到目標(biāo)數(shù)組的指定位置結(jié)束。將源數(shù)組 src從srcPos 位置開始復(fù)制到 dest 數(shù)組中，復(fù)制長(zhǎng)度為 length，數(shù)據(jù)從 dest 的 destPos 位置開始粘貼。
addAll(int index, Collection<? extends E> c)：從指定的位置開始，將指定 collection 中的所有元素插入到此列表中。
public boolean addAll(int index, Collection<? extends E> c) {
//判斷位置是否正確
if (index > size || index < 0)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
//轉(zhuǎn)換成數(shù)組
Object[] a = c.toArray();
int numNew = a.length;
//ArrayList容器擴(kuò)容處理
ensureCapacity(size + numNew); // Increments modCount
//ArrayList容器數(shù)組向右移動(dòng)的位置
int numMoved = size - index;
//如果移動(dòng)位置大于0，則將ArrayList容器的數(shù)據(jù)向右移動(dòng)numMoved個(gè)位置，確保增加的數(shù)據(jù)能夠增加
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//添加數(shù)組
System.arraycopy(a, 0, elementData, index, numNew);
//容器容量變大
size += numNew;
return numNew != 0;
}
set(int index, E element)：用指定的元素替代此列表中指定位置上的元素。
public E set(int index, E element) {
//檢測(cè)插入的位置是否越界
RangeCheck(index);
E oldValue = (E) elementData[index];
//替代
elementData[index] = element;
return oldValue;
}ArrayList 提供了 remove(int index)、remove(Object o)、removeRange(int fromIndex, int toIndex)、removeAll() 四個(gè)方法進(jìn)行元素的刪除。
remove(int index)：移除此列表中指定位置上的元素。
public E remove(int index) {
//位置驗(yàn)證
RangeCheck(index);
modCount++;
//需要?jiǎng)h除的元素
E oldValue = (E) elementData[index];
//向左移的位數(shù)
int numMoved = size - index - 1;
//若需要移動(dòng)，則想左移動(dòng)numMoved位
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
//置空最后一個(gè)元素
elementData[--size] = null; // Let gc do its work
return oldValue;
}
remove(Object o)：移除此列表中首次出現(xiàn)的指定元素（如果存在）。
public boolean remove(Object o) {
//因?yàn)锳rrayList中允許存在null，所以需要進(jìn)行null判斷
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//移除這個(gè)位置的元素
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
其中 fastRemove() 方法用于移除指定位置的元素。如下
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
}
removeRange(int fromIndex, int toIndex)：移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之間的所有元素。
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System
.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// Let gc do its work
int newSize = size - (toIndex - fromIndex);
while (size != newSize)
elementData[--size] = null;
}
removeAll()：是繼承自 AbstractCollection 的方法，ArrayList 本身并沒有提供實(shí)現(xiàn)。
public boolean removeAll(Collection<?> c) {
boolean modified = false;
Iterator<?> e = iterator();
while (e.hasNext()) {
if (c.contains(e.next())) {
e.remove();
modified = true;
}
}
return modified;
}
ArrayList 提供了 get(int index) 用讀取 ArrayList 中的元素。由于 ArrayList 是動(dòng)態(tài)數(shù)組，所以我們完全可以根據(jù)下標(biāo)來獲取 ArrayList 中的元素，而且速度還比較快，故 ArrayList 長(zhǎng)于隨機(jī)訪問。
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
在上面的新增方法的源碼中我們發(fā)現(xiàn)每個(gè)方法中都存在這個(gè)方法： ensureCapacity()，該方法就是 ArrayList 的擴(kuò)容方法。在前面就提過 ArrayList 每次新增元素時(shí)都會(huì)需要進(jìn)行容量檢測(cè)判斷，若新增元素后元素的個(gè)數(shù)會(huì)超過 ArrayList 的容量，就會(huì)進(jìn)行擴(kuò)容操作來滿足新增元素的需求。所以當(dāng)我們清楚知道業(yè)務(wù)數(shù)據(jù)量或者需要插入大量元素前，我可以使用 ensureCapacity 來手動(dòng)增加 ArrayList 實(shí)例的容量，以減少遞增式再分配的數(shù)量。
public void ensureCapacity(int minCapacity) {
//修改計(jì)時(shí)器
modCount++;
//ArrayList容量大小
int oldCapacity = elementData.length;
/*
* 若當(dāng)前需要的長(zhǎng)度大于當(dāng)前數(shù)組的長(zhǎng)度時(shí)，進(jìn)行擴(kuò)容操 作
*/
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
//計(jì)算新的容量大小，為當(dāng)前容量的1.5倍
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
//數(shù)組拷貝，生成新的數(shù)組
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
在這里有一個(gè)疑問，為什么每次擴(kuò)容處理會(huì)是 1.5 倍，而不是 2.5、3、4 倍呢？通過 google 查找，發(fā)現(xiàn) 1.5 倍的擴(kuò)容是最好的倍數(shù)。因?yàn)橐淮涡詳U(kuò)容太大(例如 2.5 倍)可能會(huì)浪費(fèi)更多的內(nèi)存(1.5 倍最多浪費(fèi) 33%，而 2.5 被最多會(huì)浪費(fèi) 60%，3.5 倍則會(huì)浪費(fèi) 71%……)。但是一次性擴(kuò)容太小，需要多次對(duì)數(shù)組重新分配內(nèi)存，對(duì)性能消耗比較嚴(yán)重。所以 1.5 倍剛剛好，既能滿足性能需求，也不會(huì)造成很大的內(nèi)存消耗。
處理這個(gè) ensureCapacity() 這個(gè)擴(kuò)容數(shù)組外，ArrayList 還給我們提供了將底層數(shù)組的容量調(diào)整為當(dāng)前列表保存的實(shí)際元素的大小的功能。它可以通過 trimToSize() 方法來實(shí)現(xiàn)。該方法可以最小化 ArrayList 實(shí)例的存儲(chǔ)量。
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
掃碼關(guān)注鍍金池微信號(hào)
手機(jī)訂課，優(yōu)惠多多