關於 ArrayList 的幾大問題，看完還不懂來打我！

作者：熬夜不加班
鏈接：https://www.jianshu.com/p/06b82a75d2af

前言

ArrayList 是 Java 集合框架中比較常用的數據結構了。繼承自 AbstractList，實現了 List 接口。底層基於數組實現容量大小動態變化。一看就是一個比較重要的模塊，所以我們今天就來學習一下 ArrayList 相關知識。

ArrayList 的數據結構和作用

ArrayList 數據結構是數組，用來裝載數據。

相對於 LinkedList，查詢效率高，因爲底層是數組，分配的是連續的內存空間，CPU 在讀取時可以緩存連續的內存空間，大幅度降低讀取的性能開銷；增刪效率低，相對於 Vector 來說是線程不安全。

雖然 ArrayList 是線程不安全的，但在我們實際的應用過程中，一般都是用來查詢，涉及到增刪的操作比較少，如果涉及到的增刪操作比較頻繁的場景，我們可以選擇 LinkedList，如果想保證線程安全，可以使用 Vector、CopyOrWriteArray。

如何實現存放任意數量的對象

ArrayList 構造器有無參構造和有參構造。在有參構造器中，ArrayList 可以通過構造方法在初始化的時候進行指定底層數組的大小。但是我們在使用有參構造時，會不會初始化數組大小呢？我們先來看一下代碼：

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 static void main(String[] args){
    //此處使用有參構造，大小爲10
    ArrayList<String> arrayList = new ArrayList<>(10);
    System.out.println("size:" + arrayList);
    arrayList.set(1, "A");
}

看到這裏是不是已經懵圈了？不要慌，我們慢慢來分析。我們的參數是 initialCapacity，這裏是將參數基於 elementData 設置的，並不是直接設置的數組大小（值得注意的是，ensureCapacity(); 方法也是這種原理）。我們也可以理解爲這個數組現在理論上最大可以裝 10 個數據，但是他現在還是空的。

在無參構造器中，初始化出一個默認空的數組，數組容量爲 0，當我們調用 add(); 方法是，默認分配【DEFAULT_CAPACITY = 10】的初始容量。下面會具體介紹新增過程，此處不再贅述。

/**
 * 數組默認初始容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 用於默認大小的空實例的共享空數組實例。 
 * 與 EMPTY_ELEMENTDATA 區分開來，以瞭解何時膨脹多少添加第一個元素。
  */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 構造一個初始空列表。
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

但是，對於無參構造和有參構造，數組都是有長度限制的，ArrayList 是通過什麼方式去實現可以存放任意數量的對象，長度沒有限制的呢？不要慌，原來這個地方也是用到了數組的擴容。

數組的擴容

當前我們有一個初始容器爲 10 的數組，且每個位置已經插滿數據，但是現在又要新增一條數據，這個時候當前數組已經不能滿足我們的要求了，那我們就需要進行擴容；

然後我們就需要進行擴容，擴大到原來的 1.5 倍，即【10 + 10 / 2】；

最後將原數組的數據原封不動地移動到新數組，再返回新數組的地址，這樣 ArrayList 中數據就是新的數組了。

接下來，我們就看一下源碼中的具體實現吧

//擴容前置判斷
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    //minCapacity: 插入數據後容器大小或者默認容器大小
    //當minCapacity比當前數組大時，說明需要擴容
    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);
    // 直接使用數組的複製方法
    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) {
    //判斷指定參數是否超過範圍
    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<? 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;
}

由代碼可知，不管是哪種插入，我們都需要通過調用 ensureCapacityInternal(); 方法來校驗數組長度，如果長度不夠，就進行擴容，前面我們已經瞭解過。對於指定位置新增時，我們在校驗完成之後通過調用 arraycopy(); 方法來實現數組的複製。下面我們就來了解一下指定位置插入的過程。

當前我們有一個長度爲 10，還有一個空位的數組；

現在我們需要插入一個【a】，目標位置是【5】，則先複製一個數組，指定位置之前的數據不變，從【5】開始把後面的數據從【5+1】的位置開始複製，新數組空出位置【5】；

上一步我們已經把【5】這個位置空出來了，然後將數據【a】插入空位，這樣就完成了指定位置插入的操作了。

由上可知，ArrayList 在新增的需要把數據複製一份，這個操作如果是針對大數據量 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;
}

由代碼可知，如果是刪除末位，則直接刪除就完成了操作；如果是將中間數據刪除，則此過程中也是類似於插入操作，將數組進行了複製，調用 arraycopy(); 方法。下面我們就來了解一下指定位置刪除的過程。

當前我們有一個長度爲 10；

現在我們需要刪除目標位置爲【5】的數據，則先複製一個數組，指定位置之前的數據不變，從【5+1】之後的數據進行復制到新數組；

得到新的數組，就是刪除了指定位置【5】數據的數組了。

同理，ArrayList 的刪除和新增一樣效率比較低。對於數據量大的數組需要複製和移動的位置就比較大了。

ArrayList 適合做隊列嗎

一般的隊列是先進先出隊列（FIFO），從尾部出入，頭部刪除。

對於數組是十分適合做隊列的，比如 ArrayBlockingQueue 內部的實現就是通過一個定長數組來實現一個環形定長隊列，使用兩個偏移量來標記數組的讀位置和寫位置，如果超過長度就折回到數組開頭。但是前提必須是一個定長的數組。

因爲在 ArrayList 中，底層雖然是數組，但是數組長度是不確定的。這樣我們就需要進行大量的增加和刪除操作，就算是指定位置的刪除和新增，它也是需要經過數組複製，這樣的話，會比較消耗性能。

因此，定長數組適合做隊列，ArrayList 不適合做隊列。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/hg-K4MpxN4p6P-r2QN2pSA

猜你喜歡