ArrayList原理解析
前言
ArrayList是Java集合框架中比較常用的數(shù)據(jù)結(jié)構(gòu)了。繼承自AbstractList，實現(xiàn)了List接口。底層基于數(shù)組實現(xiàn)容量大小動態(tài)變化。一看就是一個比較重要的模塊，所以我們今天就來學(xué)習(xí)一下ArrayList相關(guān)知識。
ArrayList的數(shù)據(jù)結(jié)構(gòu)和作用
ArrayList數(shù)據(jù)結(jié)構(gòu)是數(shù)組，用來裝載數(shù)據(jù)。
相對于LinkedList，查詢效率高，因為底層是數(shù)組，分配的是連續(xù)的內(nèi)存空間，CPU在讀取時可以緩存連續(xù)的內(nèi)存空間，大幅度降低讀取的性能開銷；增刪效率低，相對于Vector來說是線程不安全。
雖然ArrayList是線程不安全的，但在我們實際的應(yīng)用過程中，一般都是用來查詢，涉及到增刪的操作比較少，如果涉及到的增刪操作比較頻繁的場景，我們可以選擇LinkedList，如果想保證線程安全，可以使用Vector、CopyOrWriteArray。
如何實現(xiàn)存放任意數(shù)量的對象
ArrayList構(gòu)造器有無參構(gòu)造和有參構(gòu)造。在有參構(gòu)造器中，ArrayList可以通過構(gòu)造方法在初始化的時候進(jìn)行指定底層數(shù)組的大小。但是我們在使用有參構(gòu)造時，會不會初始化數(shù)組大小呢？我們先來看一下代碼：
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);
}
}
由代碼可知，我們可以很明確地得出結(jié)論：不會初始化數(shù)組大小。不信的話我們可以測試一下:
public static void main(String[] args){
//此處使用有參構(gòu)造，大小為10
ArrayList arrayList = new ArrayList<>(10);
System.out.println("size:" + arrayList);
arrayList.set(1, "A");
}
看到這里是不是已經(jīng)懵圈了？不要慌，我們慢慢來分析。我們的參數(shù)是 initialCapacity，這里是將參數(shù)基于 elementData 設(shè)置的，并不是直接設(shè)置的數(shù)組大小（值得注意的是，ensureCapacity();方法也是這種原理）。我們也可以理解為這個數(shù)組現(xiàn)在理論上最大可以裝10個數(shù)據(jù)，但是他現(xiàn)在還是空的。
在無參構(gòu)造器中，初始化出一個默認(rèn)空的數(shù)組，數(shù)組容量為 0，當(dāng)我們調(diào)用add();方法是，默認(rèn)分配【DEFAULT_CAPACITY = 10】的初始容量。下面會具體介紹新增過程，此處不再贅述。
/**
* 數(shù)組默認(rèn)初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于默認(rèn)大小的空實例的共享空數(shù)組實例。
* 與 EMPTY_ELEMENTDATA 區(qū)分開來，以了解何時膨脹多少添加第一個元素。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 構(gòu)造一個初始空列表。
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
但是，對于無參構(gòu)造和有參構(gòu)造，數(shù)組都是有長度限制的，ArrayList是通過什么方式去實現(xiàn)可以存放任意數(shù)量的對象，長度沒有限制的呢？不要慌，原來這個地方也是用到了數(shù)組的擴(kuò)容。
數(shù)組的擴(kuò)容
當(dāng)前我們有一個初始容器為10的數(shù)組，且每個位置已經(jīng)插滿數(shù)據(jù)，但是現(xiàn)在又要新增一條數(shù)據(jù)，這個時候當(dāng)前數(shù)組已經(jīng)不能滿足我們的要求了，那我們就需要進(jìn)行擴(kuò)容；
然后我們就需要進(jìn)行擴(kuò)容，擴(kuò)大到原來的1.5倍，即【10 + 10 / 2】；
最后將原數(shù)組的數(shù)據(jù)原封不動地移動到新數(shù)組，再返回新數(shù)組的地址，這樣ArrayList中數(shù)據(jù)就是新的數(shù)組了。
接下來，我們就看一下源碼中的具體實現(xiàn)吧
//擴(kuò)容前置判斷
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//minCapacity: 插入數(shù)據(jù)后容器大小或者默認(rèn)容器大小
//當(dāng)minCapacity比當(dāng)前數(shù)組大時，說明需要擴(kuò)容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//擴(kuò)容具體過程
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//此處java 8采用了位運算，提升效率
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 直接使用數(shù)組的復(fù)制方法
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList的的新增
在ArrayList中，新增有三個方法分別是以下三種：
//1\. 將指定的元素附加到此列表的末尾
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//2\. 在此指定位置插入指定元素列表。
public void add(int index, E element) {
//判斷指定參數(shù)是否超過范圍
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//3\. 將指定集合中的所有元素追加到末尾這個列表，
// 按照它們返回的順序指定集合的迭代器。
public boolean addAll(Collection 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;
}
由代碼可知，不管是哪種插入，我們都需要通過調(diào)用 ensureCapacityInternal(); 方法來校驗數(shù)組長度，如果長度不夠，就進(jìn)行擴(kuò)容，前面我們已經(jīng)了解過。對于指定位置新增時，我們在校驗完成之后通過調(diào)用 arraycopy(); 方法來實現(xiàn)數(shù)組的復(fù)制。下面我們就來了解一下指定位置插入的過程。
當(dāng)前我們有一個長度為10，還有一個空位的數(shù)組；
現(xiàn)在我們需要插入一個【a】，目標(biāo)位置是【5】，則先復(fù)制一個數(shù)組，指定位置之前的數(shù)據(jù)不變，從【5】開始把后面的數(shù)據(jù)從【5+1】的位置開始復(fù)制，新數(shù)組空出位置【5】；
上一步我們已經(jīng)把【5】這個位置空出來了，然后將數(shù)據(jù)【a】插入空位，這樣就完成了指定位置插入的操作了。
由上可知，ArrayList在新增的需要把數(shù)據(jù)復(fù)制一份，這個操作如果是針對大數(shù)據(jù)量List，再加上擴(kuò)容的操作，那效率就慢了。
ArrayList的刪除
話不多說，我們先來看一下代碼：
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;
}
由代碼可知，如果是刪除末位，則直接刪除就完成了操作；如果是將中間數(shù)據(jù)刪除，則此過程中也是類似于插入操作，將數(shù)組進(jìn)行了復(fù)制，調(diào)用arraycopy();方法。下面我們就來了解一下指定位置刪除的過程。
當(dāng)前我們有一個長度為10；
現(xiàn)在我們需要刪除目標(biāo)位置為【5】的數(shù)據(jù)，則先復(fù)制一個數(shù)組，指定位置之前的數(shù)據(jù)不變，從【5+1】之后的數(shù)據(jù)進(jìn)行復(fù)制到新數(shù)組；
得到新的數(shù)組，就是刪除了指定位置【5】數(shù)據(jù)的數(shù)組了。
同理，ArrayList的刪除和新增一樣效率比較低。對于數(shù)據(jù)量大的數(shù)組需要復(fù)制和移動的位置就比較大了。
ArrayList適合做隊列嗎
一般的隊列是先進(jìn)先出隊列（FIFO），從尾部出入，頭部刪除。
對于數(shù)組是十分適合做隊列的，比如 ArrayBlockingQueue內(nèi)部的實現(xiàn)就是通過一個定長數(shù)組來實現(xiàn)一個環(huán)形定長隊列，使用兩個偏移量來標(biāo)記數(shù)組的讀位置和寫位置，如果超過長度就折回到數(shù)組開頭。但是前提必須是一個定長的數(shù)組。
因為在ArrayList中，底層雖然是數(shù)組，但是數(shù)組長度是不確定的。這樣我們就需要進(jìn)行大量的增加和刪除操作，就算是指定位置的刪除和新增，它也是需要經(jīng)過數(shù)組復(fù)制，這樣的話，會比較消耗性能。
因此，定長數(shù)組適合做隊列，ArrayList不適合做隊列。