全面解析ArrayList，超詳細(xì)！

點(diǎn)擊藍(lán)色“程序員的時光 ”關(guān)注我 ，標(biāo)注“星標(biāo)”，及時閱讀最新技術(shù)文章

寫在前面：

小伙伴兒們，大家好！上一篇我們介紹了HashMap相關(guān)知識點(diǎn)——了解HashMap數(shù)據(jù)結(jié)構(gòu)，超詳細(xì)！

今天來學(xué)習(xí)ArrayList相關(guān)內(nèi)容，作為面試必問的知識點(diǎn)，來深入了解一波！

思維導(dǎo)圖：

1，ArrayList底層數(shù)據(jù)結(jié)構(gòu)

ArrayList就是動態(tài)數(shù)組，是List接口的可調(diào)整大小的數(shù)組實(shí)現(xiàn)；除了實(shí)現(xiàn)List接口之外，該類還提供了一些方法來操縱內(nèi)部使用的存儲列表的數(shù)組大小。它的主要底層實(shí)現(xiàn)是數(shù)組Object[] elementData。

數(shù)組的特點(diǎn)大家都知道，遍歷查詢速度快——數(shù)組在內(nèi)存是連續(xù)空間，可以根據(jù)地址+索引的方式快速獲取對應(yīng)位置上的元素。但是它的增刪速度慢——每次刪除元素，都需要更改數(shù)組長度、拷貝以及移動元素位置。

ArrayList 是 java 集合框架中比較常用的數(shù)據(jù)結(jié)構(gòu)了。繼承自 AbstractList ，實(shí)現(xiàn)了 List 接口。底層基于數(shù)組實(shí)現(xiàn)容量大小動態(tài)變化。允許 null 的存在。同時還實(shí)現(xiàn)了 RandomAccess、Cloneable、Serializable 接口，所以ArrayList 是支持快速訪問、復(fù)制、序列化的。

與ArrayList類似的是LinkedList，但是LinkedList底層是鏈表，它的數(shù)組遍歷速度慢，但增刪速度很快。

小結(jié)：

ArrayList底層是數(shù)組實(shí)現(xiàn)的存儲，查詢效率高，增刪效率低。

2，ArrayList構(gòu)造方法

下面是查看API中構(gòu)造方法

2.1，無參構(gòu)造方法

我們看源碼中的無參構(gòu)造方法：

無參構(gòu)造，使用默認(rèn)的size為10的空數(shù)組，在構(gòu)造方法中沒有對數(shù)組長度進(jìn)行設(shè)置，會在后續(xù)調(diào)用add方法的時候進(jìn)行擴(kuò)容。

里面是一個賦值操作，右邊是一個空容量數(shù)組，左邊則是存儲數(shù)據(jù)的容器，以下是參照源碼分析；

//默認(rèn)空容量數(shù)組，長度為0
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//集合真正存儲數(shù)據(jù)的容器
transient Object[] elementData; 

2.2，參數(shù)為指定初始化容量的構(gòu)造方法

來看看源碼中的int型構(gòu)造方法：

參數(shù)大于0，elementData初始化為initialCapacity大小的數(shù)組；參數(shù)等于0，elementData初始化為空數(shù)組；參數(shù)小于0，拋出異常；

2.3，參數(shù)為Collection類型的構(gòu)造方法

來看看構(gòu)造方法的源碼：

將一個參數(shù)為Collection的集合轉(zhuǎn)變?yōu)?/span>ArrayList(實(shí)際上就是將集合中的元素?fù)Q為了數(shù)組的形式)；如果傳入的集合為null會拋出空指針異常。c.toArray()可能不會正確地返回一個 Object[]數(shù)組，那么使用Arrays.copyof()方法。如果集合轉(zhuǎn)換成數(shù)組之后數(shù)組長度為0，那就直接使用自己的空成員變量初始化elementData。

總結(jié)：

上面的構(gòu)造方法理解起來比較簡單，無參構(gòu)造和初始化容量構(gòu)造的目的都是初始化底層數(shù)組elementData(this.elementData=XXX)；

無參構(gòu)造方法會將elementData初始化一個空數(shù)組，插入元素時，擴(kuò)容將會按默認(rèn)值重新初始化數(shù)組；有參構(gòu)造方法會將elementData初始化為參數(shù)值大?。?gt;=0）的數(shù)組；

如果在構(gòu)造 ArrayList 實(shí)例時，指定初始化值（初始化容量或者集合），那么就會創(chuàng)建指定大小的 Object 數(shù)組，并把該數(shù)組對象的引用賦值給 elementData；如果不指定初始化值，在第一次添加元素值時會使用默認(rèn)的容量大小 10 作為 elementData 數(shù)組的初始容量，使用 Arrays.conpyOf() 方法創(chuàng)建一個 Object[10] 數(shù)組。

一般情況下，我們用默認(rèn)的構(gòu)造方法即可。上面說到使用無參構(gòu)造時會調(diào)用add方法并進(jìn)行擴(kuò)容，下面來看看add方法以及擴(kuò)容的細(xì)節(jié)。

3，添加add()方法分析

看看ArrayList的add()添加方法：

3.1，列表的末尾添加指定元素

public boolean add(E e)

先來看看源碼分析

我們先來看第一個添加方法add(E e)，具體流程如下：

//將添加的數(shù)據(jù)傳入給e 
public boolean add(E e) { 
    //調(diào)用方法對內(nèi)部容量進(jìn)行校驗(yàn) 
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e; 
    return true; 
} 

我們看到add方法中在添加元素之前，會先判斷size的大小，所以我們來看看ensureCapacityInternal方法的細(xì)節(jié)之處

private void ensureCapacityInternal(int minCapacity) { 
        //判斷集合存數(shù)據(jù)的數(shù)組是否等于空容量的數(shù)組 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
        //通過最小容量和默認(rèn)容量 出較大值 (用于第一次擴(kuò)容) 
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 
        } 
        //將if中計(jì)算出來的容量傳遞給下一個方法,繼續(xù)校驗(yàn) 
        ensureExplicitCapacity(minCapacity); 
    } 

當(dāng) 要 add 進(jìn)第1個元素時，minCapacity為(size+1=0+1=)1，在Math.max()方法比較后，minCapacity 為10。然后緊接著調(diào)用ensureExplicitCapacity更新modCount的值，并判斷是否需要擴(kuò)容。接下來看ensureExplicitCapacity方法

private void ensureExplicitCapacity(int minCapacity) { 
        //實(shí)際修改集合次數(shù)++ (在擴(kuò)容的過程中沒用,主要是用于迭代器中) 
        modCount++; 
        //判斷最小容量    - 數(shù)組長度是否大于    0 
        if (minCapacity - elementData.length > 0) 
        //將第一次計(jì)算出來的容量傳遞給    核心擴(kuò)容方法 
        grow(minCapacity); 
    }

然后是擴(kuò)容的核心**grow()**方法：

private void grow(int minCapacity) { 
        //記錄數(shù)組的實(shí)際長度,此時由于木有存儲元素,長度為0 
        int oldCapacity = elementData.length; 
        //核心擴(kuò)容算法   原容量的1.5倍 
        int newCapacity = oldCapacity + (oldCapacity >> 1); 
        //判斷新容量-最小容量是否小于0, 如果是第一次調(diào)用add方法必然小于
        if (newCapacity - minCapacity < 0) 
        //還是將最小容量賦值給新容量 
        newCapacity = minCapacity; 
        //判斷新容量-最大數(shù)組大小是否>0,如果條件滿足就計(jì)算出一個超大容量
        if (newCapacity - MAX_ARRAY_SIZE > 0) 
        newCapacity = hugeCapacity(minCapacity); 
        // 調(diào)用數(shù)組工具類方法,創(chuàng)建一個新數(shù)組,將新數(shù)組的地址賦值給
        elementData elementData = Arrays.copyOf(elementData, newCapacity); 
}

執(zhí)行流程：

3.2，指定位置添加指定元素

public void add(int index, E element)

先來看看源碼分析

//在元素序列index位置處插入
public void add(int index, E element) {
    rangeCheckForAdd(index);
    //1，檢測是否需要擴(kuò)容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //2，將index及其之后的元素都向后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
    // 3. 將新元素插入至 index 處
    elementData[index] = element;
    size++;
}
private void rangeCheckForAdd(int index) {
    //這里判斷的index>size，index小于0，超出指定范圍就報(bào)錯
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

我們再看看它的使用方法：

import java.util.ArrayList;

/**
 * @author 公眾號:程序員的時光
 * @create 2020-11-03 17:05
 * @description
 */
public class Test03 {
    public static void main(String[] args) {
        ArrayList<String> list=new ArrayList<>();
        list.add("海心焰");
        //在index為1的位置處添加數(shù)據(jù)
        list.add(1,"玄黃炎");
        System.out.println(list);
    }
}

運(yùn)行結(jié)果：

3.3，按照指定的元素順序，將所有元素添加到此列表的尾部

public boolean addAll(Collection<? extends E> c);

這個方法的描述是，按指定集合的Iterator返回的順序?qū)⒅付现械乃性?strong style="color: rgb(119, 48, 152);">追加到此列表的末尾。

簡單來講，就是將一個集合的元素全部添加到另外一個集合中去。

運(yùn)行結(jié)果：

3.4，將指定集合中的所有元素插入到此列表中，從指定位置開始

public boolean addAll(int index, Collection<? extends E> c);

這個方法和上面的方法都是把一個集合中的元素添加到另外一個集合中去，不同的在于上面的方法是默認(rèn)添加至目標(biāo)集合的尾部，而此方法是包含索引的，也就是在指定位置開始插入元素。

運(yùn)行結(jié)果：

4，其他方法分析

ArrayList包括很多方法，我們來簡單回顧一下。

//移除指定位置上的元素
public E remove(int index);
//移除此列表中首次出現(xiàn)的指定元素（如果存在）
boolean remove(Object o);
//修改集合元素
public E set(int index, Object o);
//查找集合元素
public E get(int index);
//清空集合所有數(shù)據(jù)
public void clear();  
//判斷集合是否包含指定元素
public boolean contains(Object o);
//判斷集合是否為空
public boolean isEmpty()

5，常見面試題（精華）

5.1，ArrayList是如何擴(kuò)容的？

這個請參照3.1章節(jié)的擴(kuò)容步驟，來看看它的核心擴(kuò)容方法：

總結(jié)：

1. 擴(kuò)容的大小是原先數(shù)組的1.5倍；
2. 若值newCapacity比傳入值minCapacity還要小，則使用傳入minCapacity，若newCapacity比設(shè)定的最大容量大，則使用最大整數(shù)值；

5.2，ArrayList頻繁擴(kuò)容導(dǎo)致性能下降，如何處理？

比方說現(xiàn)在需要往數(shù)組里添加10w條數(shù)據(jù)，我們來看看前后的時間變化：

結(jié)果是：

ArrayList底層是數(shù)組實(shí)現(xiàn)的，那么每次添加數(shù)據(jù)時會不斷地?cái)U(kuò)容，這樣的話會占內(nèi)存，性能低，所以導(dǎo)致時間很長。

我們可以用ArrayList的指定初始化容量的構(gòu)造方法來解決性能低的問題。

5.3，ArrayList在增刪元素的時候是怎么進(jìn)行的，還有為何很慢？

在前面我們說過，它有按照索引添加，也有直接添加的。在這之前需要校驗(yàn)長度問題ensureCapacityInternal，如果長度不夠，則需要進(jìn)行擴(kuò)容操作。

而前面的擴(kuò)容是擴(kuò)大原來的1.5倍，采用位運(yùn)算，右移一位。

如果后面的數(shù)據(jù)量級過大，在100萬條數(shù)據(jù)中新增一個元素，后面的元素都要拷貝以及移動位置，所以說效率很低。

5.4，ArrayList是線程安全的嗎？

ArrayList線程是不安全的。線程安全的數(shù)組容器是Vector，它的原理是把所有的方法都加上synchronized。

我們來測試一下，先準(zhǔn)備一個線程任務(wù)類：

然后定義測試類，對任務(wù)類進(jìn)行測試：

我們來看結(jié)果：

可以看到會報(bào)異常錯誤，有的線程還是為null，這說明ArrayList線程是不安全的。

當(dāng)然可以用線程安全的集合Vector來代替ArrayList

或者我們可以直接加synchronized關(guān)鍵字，把不安全的線程變成安全的：

這樣也是可以保證線程安全的。

為啥ArrayList線程不安全？

線程不安全：

線程安全就是多線程訪問時，采用了加鎖機(jī)制，當(dāng)一個線程訪問該類的某個數(shù)據(jù)時，進(jìn)行保護(hù)，其他線程不能進(jìn)行訪問直到該線程讀取完，其他線程才可使用。不會出現(xiàn)數(shù)據(jù)不一致或者數(shù)據(jù)污染。

線程不安全就是不提供數(shù)據(jù)訪問保護(hù)，有可能出現(xiàn)多個線程先后更改數(shù)據(jù)造成所得到的數(shù)據(jù)是臟數(shù)據(jù)。

List接口下面有兩個實(shí)現(xiàn)，一個是ArrayList，另外一個是Vector。從源碼的角度分析，因?yàn)閂ector的方法前加了synchronized關(guān)鍵字。

ArrayList在添加一個元素時，有兩步來完成，1. 在 Items[Size] 的位置存放此元素；2. 增大 Size 的值。

在單線程運(yùn)行的情況下，如果 Size = 0，添加一個元素后，此元素在位置 0，而且 Size=1；

而如果是在 多線程情況下，比如有兩個線程，線程 A 先將元素存放在位置 0。但是此時 CPU 調(diào)度線程A暫停，線程 B 得到運(yùn)行的機(jī)會。線程B也向此 ArrayList 添加元素，因?yàn)榇藭r Size 仍然等于 0（注意哦，我們假設(shè)的是添加一個元素是要兩個步驟哦，而線程A僅僅完成了步驟1），所以線程B也將元素存放在位置0。然后線程A和線程B都繼續(xù)運(yùn)行，都增加 Size 的值。

那好，我們來看看 ArrayList 的情況，元素實(shí)際上只有一個，存放在位置 0，而 Size 卻等于 2。這就是“線程不安全”了。

5.5，ArrayList和LinkedList區(qū)別

1. 底層數(shù)據(jù)結(jié)構(gòu)：ArrayList底層使用的是數(shù)組；LinkedList底層使用的是雙向鏈表；
2. 插入和刪除元素操作：ArrayList采用的是數(shù)組存儲，所以插入和刪除元素是跟元素的位置有關(guān)系。LinkedList采用的是鏈表存儲，刪除元素是不受元素位置影響的；如果是要在指定位置i插入和刪除的話（（add(int index，E element））時間復(fù)雜度近似為O(n)，因?yàn)樾枰纫苿釉俨迦搿?/span>
3. 隨機(jī)訪問：ArrayList對于隨機(jī)元素訪問的效率明顯比LinkedList高。隨機(jī)訪問就是通過元素的索引來獲取元素（也就是set和get(int index)方法）。
4. 線程不安全：ArrayList和LinkedList都是不同步的，也就是說都是線程不安全的。
5. 接口實(shí)現(xiàn)：ArrayList實(shí)現(xiàn)了RandomAccess可以支持隨機(jī)元素訪問，而LinkedList實(shí)現(xiàn)了Deque可以當(dāng)做隊(duì)列使用
6. 內(nèi)存空間占用情況：ArrayList的空間占用主要體現(xiàn)在list列表的末尾會有一定的容量空間，它的優(yōu)勢在于內(nèi)存的連續(xù)性，CPU的內(nèi)部緩存結(jié)構(gòu)會緩存連續(xù)的內(nèi)存片段，可以大幅度降低內(nèi)存的性能開銷，提高效率；LinkedList的空間占用體現(xiàn)在每一個元素都需要消耗空間內(nèi)存，要存放前驅(qū)后繼等數(shù)據(jù)。

當(dāng)操作是在一列數(shù)據(jù)的后面添加數(shù)據(jù)而不是在前面或中間,并且需要隨機(jī)地訪問其中的元素時,使用ArrayList會提供比較好的性能；

???當(dāng)操作是在一列數(shù)據(jù)的前面或中間添加或刪除數(shù)據(jù),并且按照順序訪問其中的元素時,使用LinkedList會更好。