前言

ArrayList 是開發(fā)中使用最頻繁的集合框架中的數(shù)據(jù)結(jié)構(gòu)之一了响委，而且也是面試中必問考題。所以很有必要掌握窖梁，熟練使用赘风。所以，我們將從源碼分析底層原理實現(xiàn)和面試中常用考點分析纵刘。

ArrayList 簡介

ArrayList 是 Java 集合框架中的成員之一邀窃，底層是基于數(shù)組實現(xiàn)，并且集合容量可動態(tài)變化的假哎。它繼承自 AbstractList 抽象類瞬捕，實現(xiàn)了 List 接口。同時還實現(xiàn)了 RandomAccess舵抹，Cloneable 和 Serializable 三個標記接口肪虎，說明 ArrayList 是支持快速隨機訪問，可克隆復(fù)制的惧蛹，可序列化的扇救。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
}

騰訊一面對 ArrayList 集合的面試問題刑枝，帶你通過源碼分析這些問題

3 ArrayList 源碼分析

3.1 變量

ArrayList 底層是基于數(shù)組實現(xiàn)，并且集合容量可動態(tài)變化迅腔。類中定義了一個 Object 類型的數(shù)組存儲元素仅讽，因為是 Object 類型的數(shù)組，所以也只能存儲引用數(shù)據(jù)類型钾挟，如果存儲基本數(shù)據(jù)類型（例如 int ，double等）饱岸，底層會自動將基本數(shù)據(jù)類型進行類的包裝掺出。

ArrayList 中還定義了一個記錄數(shù)組元素個數(shù)的變量，以及一個代表默認初始化容量的靜態(tài)變量苫费。

/**
 * ArrayList 中存儲元素的數(shù)組汤锨，數(shù)組的長度即集合的容量
 * 不用 private 關(guān)鍵字修飾是為了內(nèi)部類方便訪問此數(shù)組
 * transient 關(guān)鍵字修飾代表此數(shù)組不作為序列化的一部分
 */
transient Object[] elementData;
/**
 * 記錄 ArrayList 集合中實際存儲的元素個數(shù)
 */
private int size;
/**
 * 默認初始化容量
 */
private static final int DEFAULT_CAPACITY = 10;

ArrayList 中定義了兩個靜態(tài)空數(shù)組對象，主要用來當集合初始化百框，并且沒有添加任何元素時闲礼，作為一個空數(shù)組對象賦值給 elementData 數(shù)組對象，代表一個空 list铐维。那為啥要定義2個空數(shù)組對象呢柬泽？后面會細講。

/**
 * 一個共享的靜態(tài)空數(shù)組對象嫁蛇，用于空 list 集合中
 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * 一個共享的靜態(tài)空數(shù)組對象锨并，用于默認大小初始化的空 list 集合中
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

ArrayList 的父類 AbstractList 中定義了 modCount 變量，它記錄了集合被操作修改的次數(shù)睬棚，在使用迭代器 Iterator 中會被使用到第煮，因為在使用迭代器遍歷集合元素的過程中集合結(jié)構(gòu)不允許被修改（例如添加元素，刪除元素）抑党，通過比較 modCount 的值能防止在迭代的過程中集合被修改包警。

protected transient int modCount = 0;

3.2 構(gòu)造函數(shù)

ArrayList 有三個構(gòu)造函數(shù)，一個無參構(gòu)造函數(shù)底靠，一個指定集合容量大小的有參構(gòu)造函數(shù)害晦，以及一個使用指定 Collection 集合來構(gòu)造集合的構(gòu)造函數(shù)。

無參構(gòu)造函數(shù)苛骨，即初始化一個容量為10的空 list 集合篱瞎，雖說是初始化容量為10的集合，但是實際此時沒創(chuàng)建一個容量為10的數(shù)組痒芝，而只是將
DEFAULTCAPACITY_EMPTY_ELEMENTDATA 這個空數(shù)組對象賦值給 elementData 變量俐筋，只有在第一次添加元素時才創(chuàng)建一個容量的為10的數(shù)組。

/**
 * 構(gòu)造一個容量為10的空 list
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

指定初始化容量的有參構(gòu)造函數(shù)严衬，當初始化容量大于0時澄者，直接創(chuàng)建指定容量大小的數(shù)組，如果初始化容量為0，則將 EMPTY_ELEMENTDATA 空數(shù)組對象賦值給 elementData 變量粱挡。

/**
 * 構(gòu)造一個指定初始化容量大小的空 list
 */
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);
    }
}

使用指定 Collection 集合來構(gòu)造 ArrayList 對象赠幕，如果 Collection 不為空，則將其元素拷貝賦值到 elementData 中询筏，如果 Collection 為空榕堰，則還是創(chuàng)建一個空的 list，相當于 new ArrayList(0)嫌套。

/**
 * 構(gòu)造一個 list逆屡，它包含了指定 Collection 集合元素，這些元素的順序是通過集合迭代器返回元素的順序決定的
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

3.3 常用方法

• public boolean add(E e)

在 list 尾部添加一個元素踱讨，首先會將記錄對集合操作的次數(shù)加1魏蔗，然后再判斷集合容量是否足夠，不夠則進行擴容痹筛。

/**
 * 在 list 尾部添加一個元素
 */
public boolean add(E e) {
    // 修改操作次數(shù)莺治，并且是否進行擴容操作
    ensureCapacityInternal(size + 1);
    // 將新元素添加在數(shù)組尾部
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    // 如果是采用默認初始化容量10構(gòu)造的 list，則取默認初始化容量10和當前需要添加元素的下標+1的最大值來初始化 list
    // 這里就說明了為什么要定義2個空數(shù)組對象帚稠，因為通過判斷空 list 是否等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA谣旁，
    // 如果是，則使用默認的初始化容量10來進行擴容
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    // 修改次數(shù)加1
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        // 擴容
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 擴容到原來容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 最大容量為 Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 拷貝數(shù)組
    elementData = Arrays.copyOf(elementData, newCapacity);
}

• public void add(int index, E element)

在 list 指定下標位置添加一個元素，首先會檢查下標是否在范圍內(nèi)，將記錄對集合操作的次數(shù)加1罢杉，然后再判斷集合容量是否足夠，不夠則進行擴容瘟判。

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++;
}
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

• public E set(int index, E element)

修改 list 指定下標位置的元素，首先會檢查下標是否在范圍內(nèi)角溃，然后替換指定下標的元素拷获，返回舊的元素。

/**
 * Replaces the element at the specified position in this list with
 * the specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

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

將指定 Collection 的所有元素添加到 list 的尾部中去减细，還是先檢查是否需要擴容匆瓜，最后再將 Collection 集合拷貝到 list 尾部。

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;
}

• public int size()

返回集合中元素的個數(shù)

public int size() {
    return size;
}

• public boolean isEmpty()

判斷集合是否為空未蝌，即集合是否有元素

/**
 * Returns <tt>true</tt> if this list contains no elements.
 *
 * @return <tt>true</tt> if this list contains no elements
 */
public boolean isEmpty() {
    return size == 0;
}

• public boolean contains(Object o)

判斷集合是否包含某元素驮吱，主要通過 equals 方法比較是否存在某元素。

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
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;
}

• public E get(int index)

返回指定下標位置的元素萧吠，訪問速度快左冬。

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
E elementData(int index) {
    return (E) elementData[index];
}

• public Iterator iterator()

獲取 list 的迭代器，用于遍歷集合中的元素纸型。

public Iterator<E> iterator() {
    return new Itr();
}

4 常見面試題分析

4.1 ArrayList 是線程安全的嗎拇砰？

我們通過分析 ArrayList 源碼可知梅忌，對它的任何操作都是沒有加鎖的，所以在多線程場景下除破，它是線程不安全的牧氮。如果在非多線程使用場景下，我們還是使用很頻繁瑰枫，因為主要用來存儲數(shù)據(jù)踱葛，查詢比較多，增刪操作比較少光坝。

如果增刪操作比較多的話剖毯，可以使用 LinkedList，LinkedList 增刪操作速度比較快教馆。（以后我們再詳細介紹 LinkedList ）。

如果需要線程安全的話擂达，可以推薦使用 Vector 集合土铺，分析 Vector 源碼會發(fā)現(xiàn)好多方法加了 synchronized 關(guān)鍵字修飾，即同一時間只允許一個線程進行操作板鬓，所以效率比較低悲敷，但是 Vector 是線程安全的。不過JDK集合中的工具類 Collections 提供一個方法 synchronizedList 可以將線程不安全的 ArrayList 集合變成線程安全的集合對象俭令，所以 Vector 慢慢地也很少人使用了后德。

public static void main(String[] args) {

  ArrayList<String> arrayList = new ArrayList<>();
  arrayList.add("Java");
  arrayList.add("C++");
  // 封裝成線程安全的集合
  List<String> list = Collections.synchronizedList(arrayList);

}

4.2 ArrayList 優(yōu)缺點

• 優(yōu)點：查詢速度快，因為底層是基于數(shù)組實現(xiàn)抄腔，數(shù)組在內(nèi)存中是一塊聯(lián)系的內(nèi)容空間瓢湃，所以根據(jù)地址和索引的方式可以快速隨機訪問集合中的元素。
• 缺點：增刪慢赫蛇，每次添加和刪除元素绵患，都有可能涉及到數(shù)組長度的改變和元素的拷貝移動，特別是數(shù)組元素很多時比較耗時悟耘。線程不安全落蝙。

4.3 ArrayList 底層是數(shù)組實現(xiàn)的，那為什么不直接使用數(shù)組暂幼？

ArrayList 底層雖然是通過數(shù)組實現(xiàn)的筏勒，但是它內(nèi)部對數(shù)組進行了封裝，能支持自動動態(tài)擴容旺嬉，而直接使用數(shù)組的話管行，如果想要實現(xiàn)動態(tài)擴容效果，需要開發(fā)人員自己去處理擴容機制邪媳，容易出錯病瞳。而且 ArrayList 內(nèi)部封裝了許多方法（例如在指定位置添加元素揽咕，刪除指定下標的元素，遍歷集合等）方便開發(fā)人員操作集合套菜，減少開發(fā)成本亲善。

4.4 JDK 1.7 前后有什么變化？

在 JDK 1.7之前逗柴，ArrayList 初始化的時候蛹头，會直接調(diào)? this(10) 達到真正初始化創(chuàng)建數(shù)組，而在 JDK 1.7以及之后只是將靜態(tài)空數(shù)組賦值給 elementData戏溺，并沒有真正初始化容量10渣蜗，等到第一次添加元素時容量才變化為10。

再者旷祸，之前容量擴容的時候耕拷，是擴容到原來容量的1.5倍+1，而且之后是采用位操作擴容1.5倍托享，擴容速度更快骚烧。

// 1.7之前
int newCapacity = (oldCapacity * 3)/2 + 1;
// 1.7之后
int newCapacity = oldCapacity + (oldCapacity >> 1);

4.5 初始化 ArrayList 后，直接調(diào)用 set方法會怎么樣闰围？

通過源碼分析赃绊，通過構(gòu)造方法初始化 ArrayList 之后（new ArrayList(Collection<? extends E> c) 除外），不管是默認的初始化還是指定容量大小的初始化羡榴，它們底層的 size 值都是為0碧查，但是調(diào)用 set(int index, E element) 方法，它首先會檢查下標是否大于等于 size 值校仑，如果是會報錯忠售。 所以初始化后的 ArrayList 對象，不能馬上直接調(diào)用 set 方法迄沫，會報錯档痪。

// 初始化后，此時 size 的值還是為0
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 E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

[圖片上傳失敗...(image-7571a5-1626854861117)]

4.6 ArrayList 增刪為什么會慢邢滑？

通過源碼分析腐螟，對 ArrayList 集合的添加元素和刪除元素，會涉及到數(shù)組的擴容和數(shù)據(jù)拷貝困后，如果數(shù)組元素個數(shù)巨大的話乐纸，會減低速度。但是如果是在尾部插入刪除的話摇予，如果在不超出數(shù)組原有長度的話汽绢，就不會涉及數(shù)組的擴容和數(shù)據(jù)拷貝，所以這時執(zhí)行速度還是很快的侧戴。

所以我們要結(jié)合實際場景選擇合適的數(shù)據(jù)結(jié)構(gòu)宁昭，業(yè)務(wù)場景到底是增刪多跌宛，還是查詢多，增刪多我們可以選擇 LinkedList 积仗，如果是查詢多可以選擇 ArrayList 疆拘。

4.7 使用迭代器 Iterator 過程中，可以增刪元素嗎寂曹？

通過源碼分析哎迄，在獲取集合的迭代器方法中，實際是返回了 Iterator 接口的實現(xiàn)類 Itr隆圆。而且 Itr 是 ArrayList 類中的一個內(nèi)部類漱挚。

public Iterator<E> iterator() {
    return new Itr();
}

查看 內(nèi)部類 Itr ，定義了三個變量渺氧，cursor 變量指示下一個需要返回元素的下標旨涝；lastRet 變量指示當前需要返回元素的下標，-1代表不返回侣背；expectedModCount 變量在 new Itr () 時被賦值 ArrayList 集合中 modCount 變量此時的值白华。

在獲取下一個元素的方法 next() 中，會先 checkForComodification() 方法秃踩，它的作用是檢查當前 expectedModCount 的值是否等于 ArrayList 對象目前 modCount 的值，如果不相等會報錯业筏，這也就是為什么在使用迭代器的過程中憔杨，不允許對 ArrayList 對象的做增刪操作。

private class Itr implements Iterator<E> {
     int cursor;       // index of next element to return
     int lastRet = -1; // index of last element returned; -1 if no such
     int expectedModCount = modCount;
     public boolean hasNext() {
         return cursor != size;
     }
     @SuppressWarnings("unchecked")
     public E next() {
         checkForComodification();
         int i = cursor;
         if (i >= size)
             throw new NoSuchElementException();
         Object[] elementData = ArrayList.this.elementData;
         if (i >= elementData.length)
             throw new ConcurrentModificationException();
         cursor = i + 1;
         return (E) elementData[lastRet = i];
     }
     public void remove() {
         if (lastRet < 0)
             throw new IllegalStateException();
         checkForComodification();
         try {
             ArrayList.this.remove(lastRet);
             cursor = lastRet;
             lastRet = -1;
             expectedModCount = modCount;
         } catch (IndexOutOfBoundsException ex) {
             throw new ConcurrentModificationException();
         }
     }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

4.8 Arrays.asList 創(chuàng)建 ArrayList 的使用問題

Arrays.asList() 方法生成的 ArrayList 類對象蒜胖，在調(diào)用 add消别，remove等方法時會報錯。

public static void main(String[] args) {
  List<String> list = Arrays.asList("Java", "C++", "Python");
  list.add("C#"); // 這行會報錯
}

通過源碼分析台谢，Arrays.asList() 生成的 ArrayList 對象不是我們本文所講的 java.util.ArrayList寻狂，Arrays 中的內(nèi)部類 ArrayList 繼承了 AbstractList 類，但是它沒有重寫 AbstractList 類的 add 和 remove 等法朋沮，所以直接調(diào)用這些方法時會調(diào)用它父類 AbstractList 的同名方法蛇券，而 AbstractList 類中這些方法是沒有具體的實現(xiàn)操作的，而是簡單地拋出了異常樊拓。

public class Arrays {
    public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
    }
    /**
     * @serial include
     */
    private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable {
        private static final long serialVersionUID = -2764017481108945198L;
        private final E[] a;
        ArrayList(E[] array) {
            a = Objects.requireNonNull(array);
        }
        // 省略一些代碼
    }
    // 省略一些代碼
}

AbstractList 類中方法的定義如下：

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}
/**
 * {@inheritDoc}
 *
 * <p>This implementation always throws an
 * {@code UnsupportedOperationException}.
 *
 * @throws UnsupportedOperationException {@inheritDoc}
 * @throws IndexOutOfBoundsException     {@inheritDoc}
 */
public E remove(int index) {
    throw new UnsupportedOperationException();
}

4.9 ArrayList 可以存儲null值嗎纠亚？元素可以重復(fù)嗎？

ArrayList 底層是數(shù)組實現(xiàn)的筋夏，并且在添加元素的時候蒂胞。沒有對元素進行值校驗，而是直接賦值到數(shù)組中条篷，所以 ArrayList 是可以存儲 null 值骗随，并且存儲的元素是可以重復(fù)的蛤织。

/**
 * 在 list 尾部添加一個元素
 */
public boolean add(E e) {
    // 修改操作次數(shù)，并且是否進行擴容操作
    ensureCapacityInternal(size + 1);
    // 將新元素添加在數(shù)組尾部
    elementData[size++] = e;
    return true;
}

4.10 如何邊遍歷 ArrayList 元素鸿染，邊刪除指定元素指蚜？

可能有人會使用下面的方式來實現(xiàn)邊遍歷 ArrayList 元素，邊刪除指定元素：

[圖片上傳失敗...(image-2529ad-1626854861112)]

你會發(fā)現(xiàn)執(zhí)行報錯了牡昆，
ConcurrentModificationException 并發(fā)修改異常姚炕，前面我們提到使用迭代器 Iterator 遍歷集合時，不能對集合進行增刪操作（會導(dǎo)致 modCount 值變化）丢烘，而增強 for 循環(huán)底層也是使用迭代器實現(xiàn)的柱宦，所以會報錯。應(yīng)該使用 Iterator 類的 remove 方法播瞳。

騰訊一面對 ArrayList 集合的面試問題掸刊，帶你通過源碼分析這些問題

5 總結(jié)

關(guān)于 ArrayList 集合類的相關(guān)知識先介紹到這，也建議大家自己翻閱下源碼赢乓，然后寫幾個demo調(diào)試下忧侧，這樣才能更加深對它的了解。大家也可以在下方評論你遇到過的 ArrayList 面試題牌芋，我來給你解答或者一起探討蚓炬。