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