原創(chuàng)文章觉至，轉(zhuǎn)載請(qǐng)注明出處
Java程序的核心就是那些在啟動(dòng)時(shí)和運(yùn)行中所創(chuàng)建的對(duì)象剔应，如何管理這些對(duì)象是一項(xiàng)非常重要的工作。既要方便存儲(chǔ)，又要方便讀取峻贮，有時(shí)候還需要對(duì)對(duì)象進(jìn)行排序席怪，根據(jù)不同的場(chǎng)合，需要將同一類(lèi)的對(duì)象存放在一起纤控，就形成了容器的概念挂捻。
Java類(lèi)庫(kù)為我們提供了一套相當(dāng)完整的容器來(lái)解決程序運(yùn)行中對(duì)象的存儲(chǔ)問(wèn)題，其中最常用的有 List船万、Set刻撒、Queue以及 Map。上面是一張完整的 Java 框架類(lèi)庫(kù)圖耿导，其中有許多接口和抽象類(lèi)声怔，他們定義了不同種類(lèi)基礎(chǔ)容器的行為，這個(gè)系列的文章將從源碼的角度解釋圖中常用的集合類(lèi)的實(shí)現(xiàn)以及使用碎节。
線(xiàn)性的存儲(chǔ)
ArrayList 其實(shí)是一個(gè)典型的線(xiàn)性表捧搞，從名字也不難看出它與數(shù)組有莫大的關(guān)聯(lián)，其實(shí) ArrayList 內(nèi)部本身就是維護(hù)了一個(gè)數(shù)組狮荔，所有的插入、刪除等操作都是基于這個(gè)數(shù)組實(shí)現(xiàn)的介粘。
首先看一下 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[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
transient Object[] elementData;
private int size;
}
除了一些預(yù)定義的常量殖氏，ArrayList 中一共就兩個(gè)變量：用于存放對(duì)象引用的數(shù)組elementData和標(biāo)識(shí)個(gè)數(shù)的size。值得區(qū)分一下的概念是 size 和 capacity姻采，size 表示的是當(dāng)前 ArrayList 中所存放有效對(duì)象的個(gè)數(shù)雅采，而 capacity 表示的是當(dāng)前 elementData 數(shù)組的容量（即數(shù)組大小）慨亲。眾所周知數(shù)組的長(zhǎng)度一旦被指定就無(wú)法更改婚瓜，既然 ArrayList 底層使用數(shù)組來(lái)實(shí)現(xiàn)，那它又是如何做到在被調(diào)用add()方法時(shí)看上去沒(méi)有容量限制的呢刑棵？答案就是不斷的比較 size 和 capacity巴刻，然后創(chuàng)建新的數(shù)組，再將原數(shù)組的內(nèi)容復(fù)制過(guò)去蛉签，這在ArrayList內(nèi)部稱(chēng)為擴(kuò)容操作胡陪。
對(duì)象的存放
ArrayList共有三個(gè)構(gòu)造器，他們的作用都是初始化elementData數(shù)組：
// NO.1
public ArrayList() {
this(10);
}
// NO.2
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
// NO.3
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
前兩個(gè)構(gòu)造器通過(guò)指定的capacity來(lái)初始化一個(gè)空的數(shù)組：this.elementData = new Object[initialCapacity]碍舍，如果沒(méi)有initialCapacity參數(shù)則默認(rèn)為10柠座。
tips: 在新建一個(gè)ArrayList時(shí)可以預(yù)估需要的大小，以
new ArrayList(20)這種形式調(diào)用片橡，可以避免在使用ArrayList時(shí)多次擴(kuò)容妈经。
第三個(gè)構(gòu)造器接收一個(gè)Collection參數(shù)，如果你有仔細(xì)看過(guò)文章開(kāi)頭的集合框架圖不難發(fā)現(xiàn)ArrayList是Collection的一種實(shí)現(xiàn)，這個(gè)構(gòu)造器表示可以接收Collection接口的所有實(shí)現(xiàn)類(lèi)型吹泡，并將其轉(zhuǎn)換為自身類(lèi)型（ArrayList）進(jìn)行存儲(chǔ)录煤。
擴(kuò)容與移位
要想將對(duì)象放入 ArrayList 中需要調(diào)用add(E)或者add(int, E)方法，前者將對(duì)象按順序放到末尾荞胡，后者可以指定放置的位置妈踊。
//...
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//...
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
在調(diào)用兩種 add 方法時(shí)都需要先調(diào)用ensureCapacityInternal，這個(gè)方法的做用是將數(shù)組進(jìn)行擴(kuò)容泪漂。由于在真正擴(kuò)容之前 JDK 會(huì)進(jìn)行一些邏輯檢查和判斷廊营，最終調(diào)用到grow()函數(shù)，出于篇幅考慮將一些函數(shù)的調(diào)用關(guān)系省略掉萝勤，有興趣的朋友可以自行查閱源碼露筒。先看看grow()函數(shù)中關(guān)鍵的部分：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
可以看到參數(shù) minCapacity 只是一個(gè)“建議”值煮盼，ArrayList 默認(rèn)每次擴(kuò)容為當(dāng)前容量的1.5倍：
int newCapacity = oldCapacity + (oldCapacity >> 1);
在擴(kuò)充到1.5倍之后如果還沒(méi)有達(dá)到 minCapacity 時(shí)扁位，便會(huì)采用 minCapacity 的值办斑，最后調(diào)用 Arrays.copyOf(elementData, newCapacity);將整個(gè)數(shù)組進(jìn)行拷貝伞芹。
回到add(int, E)方法第股，數(shù)組擴(kuò)容完后达址，需要在指定的位置插入元素铃彰，接著便調(diào)用了System.arraycopy趴俘，根據(jù)參數(shù)可以看出這一步將 elementData 數(shù)組第index之后的元素全部向后移了一位蜗巧，再在 index 位置插入新元素掌眠。
至此，對(duì)象的存放完成幕屹，通過(guò)對(duì)擴(kuò)容和移位的分析蓝丙，可以看出基于數(shù)組實(shí)現(xiàn)的 ArrayList 在對(duì)象的插入操作上效率并不高，但是數(shù)組的優(yōu)點(diǎn)是快速的隨機(jī)訪問(wèn)望拖，在接下來(lái)的對(duì)象獲取方法中將可以看到 ArrayList 很好的繼承了數(shù)組的這一特性渺尘。
對(duì)象的獲取
ArrayList 最常用的get(int index)方法一共只有兩行：
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//...
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
在檢查完參數(shù) index 的范圍之后，直接就返回 index 位置上的元素说敏，非撑父快速。
另一個(gè)獲取對(duì)象有關(guān)的常用函數(shù)是indexOf(Object o)像云，到這里讀者應(yīng)該可以想到基于數(shù)組的 ArrayList 是怎樣查找元素在數(shù)組中的下標(biāo)了锌雀，遍歷：
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
通過(guò)源碼可以觀察到比較有趣的一點(diǎn)，indexOf的參數(shù)允許為 null迅诬，并且如果數(shù)組中有值為 null的元素（在 size 范圍以?xún)?nèi)）時(shí)將返回下標(biāo)腋逆。
調(diào)用remove(int index)函數(shù)同樣會(huì)使數(shù)組中多個(gè)元素位置變動(dòng)：
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; // clear to let GC do its work
return oldValue;
}
同樣是調(diào)用 arraycopy方法，只不過(guò)拷貝的位置與 add 時(shí)相反侈贷。同時(shí)注意到elementData[--size] = null;是非常關(guān)鍵的惩歉，正如注釋所說(shuō)等脂，進(jìn)行remove操作以后，數(shù)組最后一個(gè)位置上引用的對(duì)象邏輯上已經(jīng)被“移除”撑蚌，但是實(shí)際數(shù)組還保持著對(duì)象的引用上遥，這會(huì)導(dǎo)致 GC 無(wú)法將其回收，造成內(nèi)存泄露争涌。
功能性函數(shù)
介紹完了主要操作函數(shù)粉楚，ArrayList 封裝的一些功能函數(shù)也非常有意思。
- trimToSize：
這個(gè)函數(shù)的作用是將數(shù)組容量（capacity）修整到 size 的大小亮垫。譬如ArrayList在大量讀入對(duì)象之后又進(jìn)行了許多移除操作模软，并且預(yù)計(jì)在今后很長(zhǎng)一段時(shí)間容量都將保持在較小范圍內(nèi)，這時(shí)可以手動(dòng)都用trimToSize()來(lái)節(jié)約內(nèi)存空間饮潦。
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
- addAll:
addAll 方法接收一個(gè)實(shí)現(xiàn)了 Collection 接口的類(lèi)型燃异，并將其添加到當(dāng)前 ArrayList 末尾：
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
其實(shí)質(zhì)最終還是調(diào)用了 arraycopy 方法，ArrayList.addAll()方法很容易讓人聯(lián)想到定義在 Collections 中的 addAll 方法继蜡，在沒(méi)有特殊要求的時(shí)候兩者可以互換回俐，個(gè)別情況下由于其實(shí)現(xiàn)邏輯不同兩者的性能會(huì)有一些差異，這里不做過(guò)多討論稀并，開(kāi)發(fā)者可以根據(jù)編程風(fēng)格和規(guī)范自行選擇仅颇，Collections.addAll()的定義如下：
public static <T> boolean addAll(Collection<? super T> c, T... elements) {
boolean result = false;
for (T element : elements)
result |= c.add(element);
return result;
}
小結(jié)
ArrayList 正如其名字，是實(shí)現(xiàn)了 List接口規(guī)范稻轨，底層采用數(shù)組的一個(gè)集合類(lèi)灵莲。ArrayList 繼承了數(shù)組的所有優(yōu)缺點(diǎn)，并且在使用上針對(duì) List 接口進(jìn)行了封裝殴俱，例如在指定位置插入、刪除元素等枚抵。開(kāi)發(fā)人員在使用時(shí)可以完全按照 List 接口定義的規(guī)范進(jìn)行調(diào)用线欲，但是知道其底層實(shí)現(xiàn)細(xì)節(jié)對(duì)程序調(diào)優(yōu)、不同集合類(lèi)之間的選擇有很大的幫助汽摹。
